Publications & Talks

Papers

Raphael Bost, and Pierre-Alain Fouque - ePrint

After the development of practical searchable encryption constructions, allowing for secure searches over an encrypted dataset outsourced to an untrusted server, at the expense of leaking some information to the server, many new attacks have recently been developed, targeting this leakage in order to break the confidentiality of the dataset or of the queries, through leakage abuse attacks.

These works helped to understand the importance of considering leakage when analyzing the security of searchable encryption schemes, but did not explain why these attacks were so powerful despite the existence of rigorous security definitions and proofs, or how they could be efficiently and provably mitigated.

This work addresses these questions by first proposing an analysis of existing leakage abuse attacks and a way to capture them in new security definitions. These new definitions also help us to devise a way to thwart these attacks and we apply it to the padding of datasets, in order to hide the number of queries’ results, and to provide provable security of some schemes with specific leakage profile against some common classes of leakage abuse attacks.

Finally, we give experimental evidence that our countermeasures can be implemented efficiently, and easily applied to existing searchable encryption schemes.

Raphael Bost, Brice Minaud and Olga Ohrimenko - CCS 2017

Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be desirable that updates do not reveal any information a priori about the modifications they carry out, and that deleted results remain inaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, backward privacy, has been overlooked.

In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions for different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with various efficiency trade-offs.

Our constructions crucially rely on primitives such as constrained pseudo-random functions and puncturable encryption schemes. Using these advanced cryptographic primitives allows for a fine-grained control of the power of the adversary, preventing her from evaluating functions on selected inputs, or decrypting specific ciphertexts. In turn, this high degree of control allows our SSE constructions to achieve the stronger forms of privacy outlined above. As an example, we present a framework to construct forward-private schemes from range-constrained pseudo-random functions.

Finally, we provide experimental results for implementations of our schemes, and study their practical efficiency.

Raphael Bost - CCS 2016

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 works showed that dynamic schemes – in which the data is efficiently updatable – leaking some informations on updated keywords are subjects to devastating adaptative attacks breaking the queries’ privacy. 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 Σoϕoς 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 Σoϕoς is an optimal point of the security/performance tradeoff for SSE.
Finally, an implementation and evaluation results demonstrate its practical efficiency.

Raphael Bost and Olivier Sanders - AsiaCrypt 2016

Tweakable blockcipher (TBC) is a powerful tool to design authenticated encryption schemes as illustrated by Minematsu’s Offset Two Rounds (OTR) construction. It considers an additional input, called tweak, to a standard blockcipher which adds some variability to this primitive. More specifically, each tweak is expected to define a different, independent pseudo-random permutation.
In this work we focus on OTR’s way to instantiate a TBC and show that it does not achieve such a property for a large amount of parameters. We indeed describe collisions between the input masks derived from the tweaks and explain how they result in practical attacks against this scheme, breaking privacy, authenticity, or both, using a single encryption query, with advantage at least 1/4.
We stress however that our results do not invalidate the OTR construction as a whole but simply prove that the TBC’s input masks should be designed differently.

Raphael Bost, Pierre-Alain Fouque and David Pointcheval - ePrint

Symmetric Searchable Encryption (SSE) is a very efficient and practical way for data owners to outsource storage of a database to a server while providing privacy guarantees. Such SSE schemes enable clients to encrypt their database while still performing queries for retrieving documents matching some keyword. This functionality is interesting to secure cloud storage, and efficient schemes have been designed in the past. However, security against malicious servers has been overlooked in most previous constructions and these only addressed security against honest-but-curious servers.
In this paper, we study and design the first efficient SSE schemes provably secure against malicious servers. First, we give lower bounds on the complexity of such verifiable SSE schemes. Then, we construct generic solutions matching these bounds using efficient verifiable data structures. Finally, we modify an existing SSE scheme that also provides forward secrecy of search queries, and make it provably secure against active adversaries, without increasing the computational complexity of the original scheme.

Raphael Bost, Raluca Ada Popa, Stephen Tu and Shafi Goldwasser - NDSS 2015

Machine learning classification is used in numerous settings nowadays, such as medical or genomics predictions, spam detection, face recognition, and financial predictions. Due to privacy concerns, in some of these applications, it is important that the data and the classifier remain confidential.
In this work, we construct three major classification protocols that satisfy this privacy constraint: hyperplane decision, Naïve Bayes, and decision trees. We also enable these protocols to be combined with AdaBoost. At the basis of these constructions is a new library of building blocks for constructing classifiers securely; we demonstrate that this library can be used to construct other classifiers as well, such as a multiplexer and a face detection classifier.
We implemented and evaluated our library and classifiers. Our protocols are efficient, taking milliseconds to a few seconds to perform a classification when running on real medical datasets.


Presentations

Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives

ACM CCS 2017 (Dallas, TX) — November 1st, 2017

Searchable Encryption: From Theory to Implementation

ENS (Paris, France) — June 28th, 2017

Forward Secure Searchable Encryption and Beyond

MIT (Boston, MA) — February 22nd, 2017
Brown University (Providence, RI) — February 15th, 2017

Trick or Tweak: On the (In)security of OTR's Tweaks

IACR Asiacrypt 2016 (Hanoi, Vietnam) — December 6th, 2016

Σoφoς – Forward Secure Searchable Encryption

ACM CCS 2016 (Vienna, Austria) — October 23rd, 2016
Microsoft Research (Cambridge, UK) — July 13th, 2016

Verifiable Symmetric Searchable Encryption

EMSEC's Séminaire Dromadaire (Rennes) — March 9th, 2016

Machine Learning Classification over Encrypted Data

NDSS 2015 (San Diego, CA) — February 10th, 2015
MIT (Boston, MA) — February 6th, 2015