Efficient Multi-user Similarity Search Over Encrypted Data in Cloud Storage

Abstract

In cloud-assisted data outsourcing systems, the privacy of sensitive data is a major concern. Thus, data are uploaded in encrypted form in many cloud applications while providing some basic yet critical functionalities, such as the ability to search. Similarity search over encrypted data provides decryptionless similarity testing between data and search queries which are encrypted by the data owner and users, respectively. However, previous similarity search schemes supporting multi-user settings incur unreasonable communication costs between the users and data owners during the search. In this paper, we propose efficient multi-user similarity search schemes for cloud storage. Specifically, the proposed schemes enable flexible similarity searches over encrypted data even when the given data have different format, encoding, or editing. The proposed similarity search schemes can guarantee asymptotically optimal performance for multi-user settings. We rigorously prove the proposed schemes are adaptively semantic secure. We also conduct an experimental analysis to demonstrate the applicability of the proposed scheme in practical cloud systems.