Visible to the public ∑O\$\textbackslashphi\$Oς: Forward Secure Searchable Encryption

Title∑O\$\textbackslashphi\$Oς: Forward Secure Searchable Encryption
Publication TypeConference Paper
Year of Publication2016
AuthorsBost, Raphael
Conference NameProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
Date PublishedOctober 2016
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4139-4
Keywordsaudits, compositionality, Encryption, encryption audits, forward privacy, implementation, Metrics, provable security, pubcrawl, resilience, searchable symmetric encryption

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 forward private schemes whose update procedure does not leak if a newly inserted element matches previous search queries. This work proposes Sophos 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 Sophos is an optimal point of the security/performance tradeoff for SSE. Finally, an implementation and evaluation results demonstrate its practical efficiency.

Citation Keybost_o$phi$o:_2016