Multi-User Collusion-Resistant Searchable Encryption with Optimal Search Time
Yun Wang, Dimitrios Papadopoulos
Abstract
The continued development of cloud computing requires technologies that protect users' data privacy even from the cloud providers themselves. Multi-user searchable encryption is one such kind of technology. It allows a data owner to selectively enable users to perform keyword searches over her encrypted documents that are stored at a cloud server. For privacy purposes, it is important to limit what an adversarial server can infer about the encrypted documents, even if it colludes with some of the users. Clearly, in this case 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 via cross-user leakage. In this work, we propose three novel multi-user searchable encryption schemes for this setting that achieve different trade-offs between performance and leakage. Compared to previous ones, our first two schemes are the first 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.