The continued development of cloud computing requires technologies that protect users’ privacy even from the cloud service providers themselves. Searchable encryption is one such kind of technology that allows users to perform keyword search queries directly over encrypted documents stored on a remote server. Multi-user searchable encryption enables a data owner to allow multiple users to search over her encrypted document collection. For many applications, it is important to limit what an adversarial service provider can infer about the encrypted documents, even if it colludes with some of the users. Clearly, it can learn the content of documents shared with this subset of “corrupted” users, however, it is important to ensure that this collusion does not reveal information abou...[ Read more ]

The continued development of cloud computing requires technologies that protect users’ privacy even from the cloud service providers themselves. Searchable encryption is one such kind of technology that allows users to perform keyword search queries directly over encrypted documents stored on a remote server. Multi-user searchable encryption enables a data owner to allow multiple users to search over her encrypted document collection. For many applications, it is important to limit what an adversarial service provider can infer about the encrypted documents, even if it colludes with some of the users. Clearly, it can learn the content of documents shared with this subset of “corrupted” users, however, it is important to ensure that this collusion does not reveal information about parts of the dataset that are only shared with the remaining “uncorrupted” users, e.g., via cross-user leakage.

In this work, we propose three novel schemes for this setting that achieve different trade-offs between performance and leakage. Compared to previous constructions, our first two schemes are the first ones to achieve asymptotically optimal search time. Our third scheme achieves minimal user storage and forward privacy with respect to document sharing, but slightly slower search performance. We formally prove the security of our schemes under reasonable assumptions. Moreover, we implement and evaluate their performance both on a single machine and over WAN. Our experimental results are encouraging, e.g., the search computation time is in the order of a few milliseconds.