## CryptoDB

### Benoît Libert

#### Publications

Year
Venue
Title
2020
EUROCRYPT
Non-interactive zero-knowledge proofs (NIZKs) are important primitives in cryptography. A major challenge since the early works on NIZKs has been to construct NIZKs with a statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such "statistical NIZK arguments" are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models. In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are "malicious-designated-verifier" NIZKs), and moreover, they satisfy a "dual-mode" property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs. Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.
2020
PKC
Inner product functional encryption ( ${mathsf {IPFE}}$ ) [ 1 ] is a popular primitive which enables inner product computations on encrypted data. In ${mathsf {IPFE}}$ , the ciphertext is associated with a vector $varvec{x}$ , the secret key is associated with a vector $varvec{y}$ and decryption reveals the inner product $langle varvec{x},varvec{y} angle$ . Previously, it was known how to achieve adaptive indistinguishability ( $mathsf {IND}$ ) based security for ${mathsf {IPFE}}$ from the $mathsf {DDH}$ , $mathsf {DCR}$ and $mathsf {LWE}$ assumptions [ 8 ]. However, in the stronger simulation ( $mathsf {SIM}$ ) based security game, it was only known how to support a restricted adversary that makes all its key requests either before or after seeing the challenge ciphertext, but not both. In more detail, Wee [ 46 ] showed that the $mathsf {DDH}$ -based scheme of Agrawal et al. (Crypto 2016) achieves semi-adaptive simulation-based security, where the adversary must make all its key requests after seeing the challenge ciphertext. On the other hand, O’Neill showed that all $mathsf {IND}$ -secure ${mathsf {IPFE}}$ schemes (which may be based on $mathsf {DDH}$ , $mathsf {DCR}$ and $mathsf {LWE}$ ) satisfy $mathsf {SIM}$ based security in the restricted model where the adversary makes all its key requests before seeing the challenge ciphertext. In this work, we resolve the question of $mathsf {SIM}$ -based security for ${mathsf {IPFE}}$ by showing that variants of the ${mathsf {IPFE}}$ constructions by Agrawal et al. , based on $mathsf {DDH}$ , Paillier and $mathsf {LWE}$ , satisfy the strongest possible adaptive $mathsf {SIM}$ -based security where the adversary can make an unbounded number of key requests both before and after seeing the (single) challenge ciphertext. This establishes optimal security of the ${mathsf {IPFE}}$ schemes, under all hardness assumptions on which it can (presently) be based.
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.
2019
ASIACRYPT
Multi-client functional encryption (MCFE) allows $\ell$ clients to encrypt ciphertexts $(\mathbf {C}_{t,1},\mathbf {C}_{t,2},\ldots ,\mathbf {C}_{t,\ell })$ under some label. Each client can encrypt his own data $X_i$ for a label t using a private encryption key $\mathsf {ek}_i$ issued by a trusted authority in such a way that, as long as all $\mathbf {C}_{t,i}$ share the same label t, an evaluator endowed with a functional key $\mathsf {dk}_f$ can evaluate $f(X_1,X_2,\ldots ,X_\ell )$ without learning anything else on the underlying plaintexts $X_i$. Functional decryption keys can be derived by the central authority using the master secret key. Under the Decision Diffie-Hellman assumption, Chotard et al. (Asiacrypt 2018) recently described an adaptively secure MCFE scheme for the evaluation of linear functions over the integers. They also gave a decentralized variant (DMCFE) of their scheme which does not rely on a centralized authority, but rather allows encryptors to issue functional secret keys in a distributed manner. While efficient, their constructions both rely on random oracles in their security analysis. In this paper, we build a standard-model MCFE scheme for the same functionality and prove it fully secure under adaptive corruptions. Our proof relies on the Learning-With-Errors ($\mathsf {LWE}$) assumption and does not require the random oracle model. We also provide a decentralized variant of our scheme, which we prove secure in the static corruption setting (but for adaptively chosen messages) under the $\mathsf {LWE}$ assumption.
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.

Asiacrypt 2020
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