Cryptographie

Searchable encryption enables a client to encrypt data, and outsource its storage to an untrusted server, while retaining the ability to issue search queries over the outsourced data. For efficiency reasons, all practical constructions in this area allow for the host server to learn a limited amount of information on the encrypted data as it processes queries, expressed in the security model by a leakage function. In this talk, I will give a short introduction to searchable encryption, and focus on the implications of very general (and seemingly innocuous) leakage functions. We will see that the problem of reconstructing the contents of the database from leakage information is closely related to statistical learning theory. Using this new viewpoint, I will present attacks that approximately reconstruct the contents of an entire database using only the access pattern leakage of range queries, a minimal type of leakage present in all practical constructions today.

Functional encryption (FE) is an advanced cryptographic primitive which allows, for a single encrypted message, to finely control how much information on the encrypted data each receiver can recover. To this end many functional secret keys are derived from a master secret key. Each functional secret key allows, for a ciphertext encrypted under the associated public key, to recover a specific function of the underlying plaintext. However constructions for general FE are far from practical, or rely on  non-standard and ill-understood cryptographic assumptions. In this talk I will focus on the construction of efficient FE schemes for linear functions (i.e. the inner product functionality), and the framework in which our constructions hold. Such schemes yield many practical applications, and our constructions are the first FE schemes for inner products modulo a prime that are both efficient and recover the result whatever its size I will also describe an instantiation of the framework using class groups of imaginary quadratic fields.

In this talk, I will present new and simple candidate PRFs introduced in a recent work. In this work, we depart from the traditional approaches for building PRFs used in provable security or in applied cryptography by exploring a new space of plausible PRF candidates. Our guiding principle is to maximize simplicity while optimizing complexity measures that are relevant to advanced cryptographic applications. Our primary focus is on weak PRFs computable by very simple circuits (depth-2 ACC circuits). The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory. On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). In particular, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity compared to protocols obtained by combining standard MPC protocols with practical PRFs (included MPC-friendly ones). Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We give a candidate EI-PRF based on our main weak PRF candidate. Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu, published at TCC 2018

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, there are still many cases for which we do not know whether the quantum security holds or not. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then the Fiat-Shamir transform is quantum secure, for a suitable choice of commitment scheme. We use our results to prove the security of a multivariate signature scheme closely related to the post-quantum signature MQDSS submitted at the NIST competition.