Sophos - Forward Secure Searchable Encryption

Abstract
Searchable Symmetric Encryption (SSE) 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 but 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. I will also explain why Sophos is an optimal point of the security/performance tradeoff for SSE. Finally, I will try to give insights into important and interesting problems about SSE.

Bio
Raphael Bost is an engineer in the 'Cryptographic Algorithms' lab at the Direction Générale pour l'Armement (the French defense procurement agency), and a PhD student at Université de Rennes 1 (France).His research interests cover applied and 'real world' cryptography, in particular secure outsourced storage and searchable encryption, and more generally computer security. Raphael graduated from Ecole Polytechnique (France) and received his M.Sc. from Brown University. He also visited the MIT in 2013.