Paper 2018/018

Multi-Key Searchable Encryption, Revisited

Ariel Hamlin, abhi shelat, Mor Weiss, and Daniel Wichs

Abstract

We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server. This setting was considered by Popa et al. (NSDI '14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS '16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob's search queries is lost. In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in PKC 2018
Keywords
Searchable EncryptionKeyword SearchMulti-UserObfuscationDigital Signatures
Contact author(s)
mormorweiss @ gmail com
History
2018-05-31: last of 3 revisions
2018-01-04: received
See all versions
Short URL
https://ia.cr/2018/018
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/018,
      author = {Ariel Hamlin and abhi shelat and Mor Weiss and Daniel Wichs},
      title = {Multi-Key Searchable Encryption, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2018/018},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/018}},
      url = {https://eprint.iacr.org/2018/018}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.