## CryptoDB

### Benoît Libert

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

#### Publications

**Year**

**Venue**

**Title**

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.

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

- 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 (1)
- 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)
- Mark Manulis (1)
- Noel McCullagh (1)
- Fabrice Mouhartem (3)
- Khoa Nguyen (7)
- Rafail Ostrovsky (1)
- Elie de Panafieu (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 (1)
- Damien Vergnaud (3)
- Huaxiong Wang (7)
- Moti Yung (15)