Cryptology ePrint Archive: Report 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.

Category / Keywords: applications / symmetric searchable encryption, provable security, implementation

Original Publication (with minor differences): 23rd ACM Conference on Computer and Communications Security (CCS), 2016

Date: received 24 Jul 2016, last revised 11 Oct 2016

Contact author: raphael_bost at alumni brown edu

Available format(s): PDF | BibTeX Citation

Version: 20161011:165632 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]