Asymptotically Optimal and Secure Multiwriter/Multireader Similarity Search

Privacy-preserving similarity search is a method of data retrieval from potentially untrusted hosts based on the similarity between encrypted data items. In this setting, a major concern is how to support searches when multiple users (multireader) request for searching similar items over data encrypted by multiple data owners (multiwriter). Unfortunately, previous similarity search schemes address this by enforcing users to communicate with data owners. This limitation incurs a significant communication overhead. Moreover, these schemes use deterministic algorithms to encrypt data, which not only violates the privacy of data but also complicates the proof of semantic security. In this paper, we propose an efficient and secure multiwriter/multireader similarity search scheme over encrypted data in cloud storage. In the proposed scheme, the cloud server is able to perform searches without incurring any interaction between users and data owners. Thus, we achieve asymptotically optimal communication cost. We provide rigorous proofs of data privacy in the standard model. Then, we show the proposed scheme achieves semantic security based on the data privacy. An in-depth experiment on an INRIA image dataset demonstrates the practicality of the proposed scheme.