The acceptability of a location-based service (LBS) hinges on its ability to efficiently provide service while protecting both the privacy of the customer and the server's economic interests. These include the privacy of the user, point-of-interests (POIs) privacy of the service provider, and provision for anonymous payment. Existing schemes fulfill these requirements only partially. Most of the schemes protect the query privacy of the user and the privacy of the services provided by the server, however, at high computation and communication costs. We propose a privacy-provisioning location-based service(P2LBS) scheme that provides unconditional privacy to the user's query and protects the basket of services offered by the service provider from unnecessary revelation along with an inbuilt anonymous payment scheme. To ensure the authentication of the user and the server, the P2LBS scheme uses a ring signature and anonymous payment protocol respectively. Query privacy and the services' reply privacy are provided through an oblivious transfer (OT) protocol. Results show that the P2LBS scheme is efficient compared to other current state-of-the-art schemes in terms of communication and computation costs. It fulfills all the end-to-end requirements needed to make an LBS scheme viable.

Query content privacy and location privacy of the user and point of interest (POI) of the service provider are a serious concern for location-based services (LBS). The current LBS schemes either protect the query content privacy or location privacy. To protect query content of the user and POI of the server, several schemes have been proposed based on${k}$-anonymity, Oblivious transfer (OT), private information retrieval (PIR), and homomorphic encryption. To protect location privacy, the existing schemes either use cryptographic schemes or need a trusted third party (TTP) between the server and the user. A change of location requires re-execution of the core scheme, which causes communication and computational overhead. To address these problems, we propose a linkable location-based services (L2BS) scheme that uses Modified Linkable Spontaneous Anonymous Group (MLSAG) signature scheme and the OT scheme. The proposed MLSAG scheme provides privacy-preserving authentication with privacy preserving service linking. The OT protocol protects the query content of the user and the POI of the server. When a user requests for service and sends a query to the same server second time onwards, the L2BS scheme does not require re-execution of the OT. This, L2BSWOT scheme, decreases the communication and computation costs in addition to privacy-preserving linking of past and current queries from the same user. Results show that L2BS scheme with or without the need for OT execution (L2BSWOT scheme) outperforms other existing LBS schemes in terms of communication and computation costs while satisfying all privacy requirements of an LBS.