Paper 2016/728

Sophos - Forward Secure Searchable Encryption

Raphael Bost

Abstract

Searchable Symmetric Encryption aims at making possible searching over an encrypted database stored on an untrusted server while keeping privacy of both the queries and the data, by allowing some small controlled leakage to the server. Recent work shows that dynamic schemes -- in which the data is efficiently updatable -- leaking some information on updated keywords are subject to devastating adaptative attacks breaking the privacy of the queries. The only way to thwart this attack is to design \emph{forward private} schemes whose update procedure does not leak if a newly inserted element matches previous search queries. This work proposes ${\Sigma o\phi o\varsigma}$ as a forward private SSE scheme with performance similar to existing less secure schemes, and that is conceptually simpler (and also more efficient) than previous forward private constructions. In particular, it only relies on trapdoor permutations and does not use an ORAM-like construction. We also explain why ${\Sigma o\phi o\varsigma}$ is an optimal point of the security/performance tradeoff for SSE. Finally, an implementation and evaluation results demonstrate its practical efficiency.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. 23rd ACM Conference on Computer and Communications Security (CCS), 2016
DOI
10.1145/2976749.2978303
Keywords
symmetric searchable encryptionprovable securityimplementation
Contact author(s)
raphael_bost @ alumni brown edu
History
2016-10-11: last of 2 revisions
2016-07-27: received
See all versions
Short URL
https://ia.cr/2016/728
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/728,
      author = {Raphael Bost},
      title = {Sophos -  Forward Secure Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/728},
      year = {2016},
      doi = {10.1145/2976749.2978303},
      note = {\url{https://eprint.iacr.org/2016/728}},
      url = {https://eprint.iacr.org/2016/728}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.