Cloud computing brings a lot of benefits to users, mainly in the form of flexibility and cost efficiency. But many users are worried about the privacy of sensitive data stored "in the cloud". Searchable Encryption is one of the solutions to this problem: it is a family of protocols that provide the functionality of a remote database while protecting the privacy of the data (and most of the time of the queries as well) against a potentially malicious or compromised cloud server.
In this thesis we study the extension of the notion of searchable encryption to scenarios where many users want to write to the database and want to chose who should be accessed to access his data. This is the problem of "Multi-User Searchable Encryption" (MUSE). In this thesis, we first argue that it is necessary to consider some users colluding with the server in the threat model of MUSE, a statement that was already made by other researchers in a paper presenting MKSE, the first MUSE protocol supposed to protect against this kind of threat. We then show that all existing MUSE protocols, including MKSE, are actually very vulnerable against this kind of threat. We identify the main cause of this weakeness, which happens to be fundamental and common to all existing protocols. We then design three MUSE protocols that are the first to protect against this kind of collusions. One, DH-AP-MUSE, is very fast, faster actually than MKSE. Another, RMÖ15, leaks almost no information at all to the server but does not scale well to very large databases. Finally, the RMÖ18 protocol is more involved than the other two protocols but offers more privacy than DH-AP-MUSE without the scalability issues of RMÖ15. Our research work on MUSE also led us to contribute to some cryptographic building blocks that are used in other families of protocols.
