## CryptoDB

### Benoît Libert

#### Affiliation: CNRS and ENS de Lyon, FR

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

New Constructions of Statistical NIZKs: Dual-Mode DV-NIZKs and More
📺
Abstract

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

Adaptive Simulation Security for Inner Product Functional Encryption
📺
Abstract

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 with Short Tags
Abstract

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 with More Expressive Queries
Abstract

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 for Linear Functions in the Standard Model from LWE
Abstract

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

Lattice-Based Zero-Knowledge Arguments for Integer Relations
📺
Abstract

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

Adaptively Secure Distributed PRFs from $\mathsf {LWE}$
Abstract

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

CRYPTO

2016

EUROCRYPT

2016

ASIACRYPT

2016

ASIACRYPT

2015

EPRINT

2015

EPRINT

2015

CRYPTO

2015

ASIACRYPT

2014

EUROCRYPT

2014

PKC

2014

ASIACRYPT

2012

PKC

2011

ASIACRYPT

2011

ASIACRYPT

2007

EPRINT

Certificateless Encryption Schemes Strongly Secure in the Standard Model
Abstract

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.

2005

ASIACRYPT

2004

EPRINT

The Exact Security of an Identity Based Signature and its Applications
Abstract

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

New identity based signcryption schemes from pairings
Abstract

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

Identity Based Undeniable Signatures
Abstract

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.

#### Program Committees

- 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

#### Coauthors

- Shweta Agrawal (2)
- Nuttapong Attrapadung (5)
- Paulo S. L. M. Barreto (1)
- Fabrice Benhamouda (1)
- Julien Cathalo (1)
- Alexander W. Dent (2)
- Alex Escala (1)
- Pooya Farshim (1)
- Marc Fischlin (1)
- Brett Hemenway (1)
- Javier Herranz (2)
- Marc Joye (9)
- Fabien Laguillaumie (1)
- Adeline Langlois (1)
- San Ling (6)
- Monosij Maitra (1)
- Mark Manulis (1)
- Noel McCullagh (1)
- Fabrice Mouhartem (3)
- Khoa Nguyen (7)
- Rafail Ostrovsky (1)
- Elie de Panafieu (1)
- Alain Passelègue (1)
- Kenneth G. Paterson (4)
- Thomas Peters (14)
- Chen Qian (2)
- Elizabeth A. Quaglia (2)
- Jean-Jacques Quisquater (7)
- Carla Ràfols (1)
- Amin Sakzad (1)
- Damien Stehlé (5)
- Ron Steinfeld (1)
- Benjamin Hong Meng Tan (1)
- Radu Titiu (3)
- Damien Vergnaud (3)
- Huaxiong Wang (7)
- Hoeteck Wee (1)
- David J. Wu (1)
- Moti Yung (15)