Smart Parking Services (SPSs) enable cruising drivers to find the nearest parking lot with available spots, reducing the traveling time, gas, and traffic congestion. However, drivers risk the exposure of sensitive location data during parking query to an untrusted Smart Parking Service Provider (SPSP). Our motivation arises from a repetitive query to an updated database, i.e., how a driver can be repetitively paired with a previously-matched-but-forgotten lot. Meanwhile, we aim to achieve repetitive query in an oblivious and unlinkable manner. In this work, we present Mnemosyne2 : decentralized and privacy-preserving smart parking with secure repetition and full verifiability. Specifically, we design repetitive, oblivious, and unlinkable Secure k Nearest Neighbor (SkNN) with basic verifiability (correctness and completeness) for encrypted-andupdated databases. We build a local Ethereum blockchain to perform driver-lot matching via smart contracts. To adapt to the lot count update, we resort to the immutable blockchain for advanced verifiability (truthfulness). Last, we utilize decentralized blacklistable anonymous credentials to guarantee identity privacy. Finally, we formally define and prove privacy and security. We conduct extensive experiments over a real-world dataset and compare Mnemosyne2 with existing work. The results show that a query only needs 8 seconds (175 ms) on average for service waiting (verification) among 500 drivers.

Location-Based Services (LBSs) depend on a Service Provider (SP) to store data owners’ geospatial data and to process data users’ queries. For example, a Yelp user queries the SP to retrieve the k nearest Starbucks by submitting her/his current location. It is well-acknowledged that location privacy is vital to users and several prominent Secure k Nearest Neighbor (SkNN) query processing schemes are proposed. We observe that no prior work addresses the requirement of repetitive query after index update and its privacy issue, i.e., how to match a data item from the cloud repetitively in an oblivious and unlinkable manner. Meanwhile, a malicious SP may skip some data items and recommend others due to unfair competition. In this work, we formally define the repetitive query and its privacy objectives and present an Repetitive, Oblivious, and Unlinkable SkNN scheme ROU. Specifically, we design a multi-level structure to organize locations to further improve search efficiency. Second, we integrate data item identity into the framework of existing SkNN query processing. Data owners encrypt their data item identity and location information into a secure index, and data users encrypt a customized identity range of a previously retrieved data item and location information into a token. Next, the SP uses the token to query the secure index to find the specific data item via privacy-preserving range querying. We formally prove the privacy of ROU in the random oracle model. We build a prototype based on a server to evaluate the performance with a real-world dataset. Experimental results show that ROU is efficient and practical in terms of computational cost, communication overhead, and result verification.