Multi-User Collusion-Resistant Searchable Encryption for Cloud Storage

The continued development of cloud computing requires technologies protecting users’ data privacy even from the cloud providers themselves, such as Multi-user searchable encryption. It allows data owners to selectively enable users to perform keyword searches over their encrypted data stored at a cloud server. For privacy purposes, it is important to limit what an adversarial server can infer about the encrypted data, even if it colludes with some users. Clearly, in this case it can learn the content of data shared with these “corrupted” users, however, it is important to ensure this collusion does not reveal information about parts of the dataset that are only shared with “uncorrupted” users via
cross-user
leakage. In this work, we propose three novel multi-user searchable encryption schemes eliminating cross-user 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 data sharing, but slightly slower search performance. We formally prove the security of our schemes under reasonable assumptions. Moreover, we implement them for textual documents and tabular databases and evaluate their computation and communication performance with encouraging results.