## CryptoDB

### Benoît Libert

#### Publications

Year
Venue
Title
2019
PKC
Lossy algebraic filters (LAFs) are function families where each function is parametrized by a tag, which determines if the function is injective or lossy. While initially introduced by Hofheinz (Eurocrypt 2013) as a technical tool to build encryption schemes with key-dependent message chosen-ciphertext (KDM-CCA) security, they also find applications in the design of robustly reusable fuzzy extractors. So far, the only known LAF family requires tags comprised of $\varTheta (n^2)$ group elements for functions with input space $\mathbb {Z}_p^n$, where p is the group order. In this paper, we describe a new LAF family where the tag size is only linear in n and prove it secure under simple assumptions in asymmetric bilinear groups. Our construction can be used as a drop-in replacement in all applications of the initial LAF system. In particular, it can shorten the ciphertexts of Hofheinz’s KDM-CCA-secure public-key encryption scheme by 19 group elements. It also allows substantial space improvements in a recent fuzzy extractor proposed by Wen and Liu (Asiacrypt 2018). As a second contribution, we show how to modify our scheme so as to prove it (almost) tightly secure, meaning that security reductions are not affected by a concrete security loss proportional to the number of adversarial queries.
2019
PKC
Zero-knowledge elementary databases (ZK-EDBs) are cryptographic schemes that allow a prover to commit to a set $\mathsf {D}$ of key-value pairs so as to be able to prove statements such as “x belongs to the support of $\mathsf {D}$ and $\mathsf {D}(x)=y$” or “x is not in the support of $\mathsf {D}$”. Importantly, proofs should leak no information beyond the proven statement and even the size of $\mathsf {D}$ should remain private. Chase et al. (Eurocrypt’05) showed that ZK-EDBs are implied by a special flavor of non-interactive commitment, called mercurial commitment, which enables efficient instantiations based on standard number theoretic assumptions. On the other hand, the resulting ZK-EDBs are only known to support proofs for simple statements like (non-)membership and value assignments. In this paper, we show that mercurial commitments actually enable significantly richer queries. We show that, modulo an additional security property met by all known efficient constructions, they actually enable range queries over keys and values – even for ranges of super-polynomial size – as well as membership/non-membership queries over the space of values. Beyond that, we exploit the range queries to realize richer queries such as $k$-nearest neighbors and revealing the $k$ smallest or largest records within a given range. In addition, we provide a new realization of trapdoor mercurial commitment from standard lattice assumptions, thus obtaining the most expressive quantum-safe ZK-EDB construction so far.
2018
CRYPTO
We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus q. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying $Z=X+Y$ over $\mathbb {Z}$. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities $X<Z$ among committed integers, as well as arguments showing that a committed X belongs to a public interval $[\alpha ,\beta ]$, where $\alpha$ and $\beta$ can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using $\widetilde{\mathcal {O}}(n \cdot \log |S|)$ bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations $Z=XY$ over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba’s multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.
2018
TCC
In distributed pseudorandom functions (DPRFs), a PRF secret key SK is secret shared among N servers so that each server can locally compute a partial evaluation of the PRF on some input X. A combiner that collects t partial evaluations can then reconstruct the evaluation F(SK, X) of the PRF under the initial secret key. So far, all non-interactive constructions in the standard model are based on lattice assumptions. One caveat is that they are only known to be secure in the static corruption setting, where the adversary chooses the servers to corrupt at the very beginning of the game, before any evaluation query. In this work, we construct the first fully non-interactive adaptively secure DPRF in the standard model. Our construction is proved secure under the $\mathsf {LWE}$ assumption against adversaries that may adaptively decide which servers they want to corrupt. We also extend our construction in order to achieve robustness against malicious adversaries.
2017
PKC
2017
CRYPTO
2017
ASIACRYPT
2017
ASIACRYPT
2017
JOFC
2016
EUROCRYPT
2016
CRYPTO
2016
ASIACRYPT
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
PKC
2015
CRYPTO
2015
ASIACRYPT
2014
EUROCRYPT
2014
PKC
2014
PKC
2014
ASIACRYPT
2013
PKC
2013
PKC
2013
CRYPTO
2013
ASIACRYPT
2013
EUROCRYPT
2012
TCC
2012
EUROCRYPT
2012
CRYPTO
2012
PKC
2012
ASIACRYPT
2011
PKC
2011
PKC
2011
ASIACRYPT
2011
ASIACRYPT
2010
TCC
2010
PKC
2009
ASIACRYPT
2009
PKC
2008
PKC
2008
PKC
2007
PKC
2007
EPRINT
This paper presents the first constructions for certificateless encryption (CLE) schemes that are provably secure against strong adversaries in the standard model. It includes both a generic construction for a strongly secure CLE scheme from any passively secure scheme as well as a concrete construction based on the Waters identity-based encryption scheme.
2006
PKC
2005
ASIACRYPT
2004
PKC
2004
EPRINT
This paper first positively answers the previously open question of whether it was possible to obtain an optimal security reduction for an identity based signature (IBS) under a reasonable computational assumption. We revisit the Sakai-Ogishi-Kasahara IBS that was recently proven secure by Bellare, Namprempre and Neven through a general framework applying to a large family of schemes. We show that their modified SOK-IBS scheme can be viewed as a one-level instantiation of Gentry and Silverberg's alternative hierarchical IBS the exact security of which was never considered before. We also show that this signature is as secure as the one-more Diffie-Hellman problem. As an application, we propose a modification of Boyen's "Swiss Army Knife" identity based signature encryption (IBSE) that presents better security reductions and satisfies the same strong security requirements with a similar efficiency.
2003
EPRINT
We present a new identity based scheme based on pairings over elliptic curves. It combines the functionalities of signature and encryption and is provably secure in the random oracle model. We compare it with Malone-Lee's one from security and efficiency points of view. We give a formal proof of semantical security under the Decisional Bilinear Diffie-Hellman assumption for this new scheme and we show how to devise other provably secure schemes that produce even shorter ciphertexts.
2003
EPRINT
In this paper, we give a first example of identity based undeniable signature using pairings over elliptic curves. We extend to the identity based setting the security model for the notions of invisibility and anonymity given by Galbraith and Mao in 2003 and we prove that our scheme is existentially unforgeable under the Bilinear Diffie-Hellman assumption in the random oracle model. We also prove that it has the invisibility property under the Decisional Bilinear Diffie-Hellman assumption and we discuss about the efficiency of the scheme.

PKC 2020
PKC 2019
Asiacrypt 2018
TCC 2017
Eurocrypt 2017
PKC 2016
PKC 2015
Eurocrypt 2015
PKC 2013
Asiacrypt 2013
Eurocrypt 2012
Eurocrypt 2011
PKC 2010