MUSE: Multi-User Searchable Encryption

17/ Jan/ 2018
Melek Önen

MUSE is a searchable encryption scheme that enables cloud users to upload their encrypted data and authorize other users to perform lookup queries over these data. The main privacy guarantee that MUSE offers is that it does not disclose the content of the data and the queries to the cloud.

MUSE is one of the first solutions that is suitable to the multi-user context. Furthermore, compared to existing multi-user searchable encryption solutions, this new primitive does not leak sensitive information and takes into account user-cloud collustions. Furthermore, MUSE remains scalable with respect to the number of users querying documents.

This new MUSE protocol makes use of new building blocks such as Oblivious Transfer or Garbled-Bloom Filters and is the first to ensure a high level of privacy in presence of users colluding with the CSP. Thanks to the use of an additional third party called Query Mutiplexer, whenever a user named as reader is able to efficiently search a large number of indexes, while each of these indexes is encrypted with the secret key of a different user named as writer. The new protocol is illustrated in the following figure. Writers send encrypted indexes to DH and authorizations to QM, and readers send trapdoors to QM. When QM receives a trapdoor t_(r,s) from reader r, QM multiplexes this query into several ones each of them destined to one encrypted index. DH further processes each of these queries and send the (encrypted) results to QM who further filters out negative results and send the set of indices the search query actually matched.


MUSE could be very useful in a scenario whereby individuals outsource their data to a cloud server and allow some third party services (such as recommendation systems) to perform a search over their data in order to increase their quality of service for example. Meanwhile the cloud storage server does not discover any information about the processed data.