Fingerprinting-based localization is one of the most popular indoor localization approaches.In the offline phase,the service provider measures the fingerprint,i.e.,receives signal strength (RSS) samples from various access points (APs) at a number of knownlocations in the target space and stores them in a database.In the online phase,a user sends his location query with his current fingerprint measurement to the server,which will search for the closest fingerprintin the database.Although this approach has been studied for a long time,no existing work considers the privacy requirements for the two sides:the provider wants to protect thecollected fingerprints against the users;while the users want to protect their fingerprint measurements against the service provider to avoid locationleaking.In this paper,we aim to protect the privacy of the users and the service provider at the same time.We propose a privacy-preserving fingerprint matching scheme which uses a cryptographic technique to compute the distance between the fingerprint measured by the user and the fingerprints in the database within the ciphertext space.We show that it well guarantees the privacy requirement of both the two sides in a single localization.To reduce its time overhead,we then present an improved scheme based on the grid division as well as three extensions at the cost of limited privacy loss.To enhance its security,we finally present an effective countermeasure against a special attack leveraging which malicious users could revealfingerprints on the server through repeated localizations.The extensive experiments with a public RSS-fingerprint dataset show that our proposal is fast enough for realtime localization and preserve the localization precision at the same time.