## CryptoDB

### Damien Vergnaud

#### Affiliation: ENS de Paris, France

#### Publications

**Year**

**Venue**

**Title**

2020

ASIACRYPT

Public-Key Generation with Verifiable Randomness
📺
Abstract

We revisit the problem of proving that a user algorithm selected and correctly used a truly random seed in the generation of her cryptographic key. A first approach was proposed in 2002 by Juels and Guajardo for the validation of RSA secret keys. We present a new security model and general tools to efficiently prove that a private key was generated at random according to a prescribed process, without revealing any further information about the private key.
We give a generic protocol for all key-generation algorithms based on probabilistic circuits and prove its security. We also propose a new protocol for factoring-based cryptography that we prove secure in the aforementioned model. This latter relies on a new efficient zero-knowledge argument for the double discrete logarithm problem that achieves an exponential improvement in communication complexity compared to the state of the art, and is of independent interest.

2020

ASIACRYPT

Succinct Diophantine-Satisfiability Arguments
📺
Abstract

A Diophantine equation is a multi-variate polynomial equation with integer coefficients and it is satisfiable if it has a solution with all unknowns taking integer values. Davis, Putnam, Robinson and Matiyasevich showed that the general Diophantine satisfiability problem is undecidable (giving a negative answer to Hilbert's tenth problem) but it is nevertheless possible to argue in zero-knowledge the knowledge of a solution, if a solution is known to a prover.
We provide the first succinct honest-verifier zero-knowledge argument for the satisfiability of Diophantine equations with a communication complexity and a round complexity that grows logarithmically in the size of the polynomial equation. The security of our argument relies on standard assumptions on hidden-order groups. As the argument requires to commit to integers, we introduce a new integer-commitment scheme that has much smaller parameters than Damgard and Fujisaki's scheme. We finally show how to succinctly argue knowledge of solutions to several NP-complete problems and cryptographic problems by encoding them as Diophantine equations.

2019

TCC

Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND
Abstract

We consider multi-party information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource, and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [12, 17].More concretely, we consider the randomness complexity of the basic boolean function and, that serves as a building block in the design of many private protocols. We show that and cannot be privately computed using a single random bit, thus giving the first non-trivial lower bound on the 1-private randomness complexity of an explicit boolean function, $$f: \{0,1\}^n \rightarrow \{0,1\}$$. We further show that the function and, on any number of inputs n (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $$n=3$$ players), improving the upper bound of 73 random bits implicit in [17]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for xor, which is trivially 1-random, and for several degenerate functions).

2017

TOSC

Security of Even-Mansour Ciphers under Key-Dependent Messages
Abstract

The iterated Even–Mansour (EM) ciphers form the basis of many blockcipher designs. Several results have established their security in the CPA/CCA models, under related-key attacks, and in the indifferentiability framework. In this work, we study the Even–Mansour ciphers under key-dependent message (KDM) attacks. KDM security is particularly relevant for blockciphers since non-expanding mechanisms are convenient in setting such as full disk encryption (where various forms of key-dependency might exist). We formalize the folklore result that the ideal cipher is KDM secure. We then show that EM ciphers meet varying levels of KDM security depending on the number of rounds and permutations used. One-round EM achieves some form of KDM security, but this excludes security against offsets of keys. With two rounds we obtain KDM security against offsets, and using different round permutations we achieve KDM security against all permutation-independent claw-free functions. As a contribution of independent interest, we present a modular framework that can facilitate the security treatment of symmetric constructions in models that allow for correlated inputs.

2017

CHES

Generalized Polynomial Decomposition for S-boxes with Application to Side-Channel Countermeasures
Abstract

Masking is a widespread countermeasure to protect implementations of block-ciphers against side-channel attacks. Several masking schemes have been proposed in the literature that rely on the efficient decomposition of the underlying s-box(es). We propose a generalized decomposition method for s-boxes that encompasses several previously proposed methods while providing new trade-offs. It allows to evaluate
$$n\lambda $$
-bit to
$$m\lambda $$
-bit s-boxes for any integers
$$n,m,\lambda \ge 1$$
by seeing it a sequence of mn-variate polynomials over
$$\mathbb {F}_{2^{\lambda }}$$
and by trying to minimize the number of multiplications over
$$\mathbb {F}_{2^{\lambda }}$$
.

2015

CHES

2012

PKC

2011

ASIACRYPT

2010

EPRINT

Batch Groth-Sahai
Abstract

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) and also for specific popular protocols relying on their methodology (namely Groth's group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures).

2010

EPRINT

Fair Blind Signatures without Random Oracles
Abstract

A fair blind signature is a blind signature with revocable anonymity and unlinkability, i.e., an authority can link an issuing session to the resulting signature and trace a signature to the user who requested it. In this paper we first revisit the security model for fair blind signatures given by Hufschmitt and Traor\'e in 2007. We then give the first practical fair blind signature scheme with a security proof in the standard model. Our scheme satisfies a stronger variant of the Hufschmitt-Traor\'e model.

2010

EPRINT

On The Broadcast and Validity-Checking Security of PKCS \#1 v1.5 Encryption
Abstract

This paper describes new attacks on PKCS \#1 v1.5, a deprecated but still widely used RSA encryption standard.
The first cryptanalysis is a broadcast attack, allowing the opponent to
reveal an identical plaintext sent to different recipients. This is
nontrivial because different randomizers are used for different
encryptions (in other words, plaintexts coincide only partially).
The second attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high.
The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of PKCS \#1 v1.5.

2010

EPRINT

Huff's Model for Elliptic Curves
Abstract

This paper revisits a model for elliptic curves over Q introduced by Huff in 1948 to study a diophantine problem. Huff's model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of Z/4Z×Z/2Z is birationally equivalent to a Huff curve over the original field.
This paper extends and generalizes Huff's model. It presents fast explicit formulas for point addition and doubling on Huff curves. It also addresses the problem of the efficient evaluation of pairings over Huff curves. Remarkably, the formulas we obtain feature some useful properties, including completeness and independence of the curve parameters.

#### Program Committees

- Eurocrypt 2020
- Eurocrypt 2018
- PKC 2010

#### Coauthors

- Aurélie Bauer (3)
- Sonia Belaïd (2)
- Fabrice Benhamouda (6)
- Olivier Blazy (8)
- Céline Chevalier (5)
- Jean-Sébastien Coron (1)
- Pooya Farshim (1)
- Georg Fuchsbauer (3)
- Dahmun Goudarzi (1)
- Brett Hemenway (1)
- Malika Izabachène (1)
- Amandine Jambert (1)
- Marc Joye (1)
- Louiza Khati (1)
- Eyal Kushilevitz (1)
- Fabien Laguillaumie (1)
- Benoît Libert (3)
- David Naccache (1)
- Rafail Ostrovsky (2)
- Pascal Paillier (2)
- Alain Passelègue (2)
- David Pointcheval (5)
- Emmanuel Prouff (3)
- Matthieu Rivain (1)
- Adi Rosén (1)
- Hervé Sibert (1)
- Adrian Thillard (4)
- Mehdi Tibouchi (2)
- Patrick Towa (2)
- Srinivas Vivek (1)
- Jean-Christophe Zapalowicz (1)