## CryptoDB

### Jean-Sébastien Coron

#### Affiliation: University of Luxembourg, Luxembourg

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

Side-channel Masking with Pseudo-Random Generator
📺
Abstract

High-order masking countermeasures against side-channel attacks usually require plenty of randomness during their execution. For security against t probes, the classical ISW countermeasure requires O(t^2 s) random bits, where s is the circuit size. However running a True Random Number Generator (TRNG) can be costly in practice and become a bottleneck on embedded devices. In [IKL+13] the authors introduced the notion of robust pseudo-random number generator (PRG), which must remain secure even against an adversary who can probe at most t wires. They showed that when embedding a robust PRG within a private circuit, the number of random bits can be reduced to O(t^4), that is independent of the circuit size s (up to a logarithmic factor). Using bipartite expander graphs, this can be further reduced to O(t^(3+eps)); however the resulting construction is unpractical.
In this paper we describe a practical construction where the number of random bits is only O(t^2) for security against t probes, without expander graphs; moreover the running time of each pseudo-random generation goes down from O(t^4) to O(t). Our technique consists in using multiple independent PRGs instead of a single one. We show that for ISW circuits, the robustness property of the PRG is not required anymore, which leads to simple and efficient constructions. For example, for AES we only need 48 bytes of randomness to get second-order security (t=2), instead of 2880 in the original Rivain-Prouff countermeasure; when implemented on an ARM-based embedded device with a relatively slow TRNG, we obtain a 50% speed-up compared to Rivain-Prouff.

2020

CRYPTO

A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
📺
Abstract

At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the Nguyen-Stern algorithm works quite well in practice for moderate values of n, we argue that its complexity is actually exponential in n; namely in the final step one must recover a very short basis of a n-dimensional lattice, which takes exponential-time in n, as one must apply BKZ reduction with increasingly large block-sizes.
In this paper, we describe a variant of the Nguyen-Stern algorithm that works in polynomial-time. The first step is the same orthogonal lattice attack with LLL as in the original algorithm. In the second step, instead of applying BKZ, we use a multivariate technique that recovers the short lattice vectors and finally the hidden secrets in polynomial time. Our algorithm works quite well in practice, as we can reach n=250 in a few hours on a single PC.

2020

CRYPTO

Random Probing Security: Verification, Composition, Expansion and New Constructions
📺
Abstract

Masking countermeasure is among the most powerful countermeasures to counteract side-channel attacks. Leakage models have been exhibited to theoretically reason on the security of such masked implementations. So far, the most widely used leakage model is the probing model defined by Ishai, Sahai, and Wagner at (CRYPTO 2003). While it is advantageously convenient for security proofs, it does not capture an adversary exploiting full leakage traces as, e.g., in horizontal attacks. Those attacks target the multiple manipulation of the same share to average a constant noise and recover the corresponding value. To capture a wider class of attacks another model was introduced and is referred to as the random probing model. From a leakage parameter p, each wire of the circuit leaks its value with probability p. While this model much better reflects the physical reality of side channels, it requires more complex security proofs and does not yet come with practical constructions.
In this paper, we define the first framework dedicated to the random probing model. We provide an automatic tool, called VRAPS, to quantify the random probing security of a circuit from its leakage probability. We also formalize a composition property for secure random probing gadgets and exhibit its relation to the strong non-interference (SNI) notion used in the context of probing security. We then revisit the expansion idea proposed by Ananth, Ishai, and Sahai (CRYPTO 2018) and introduce a compiler that builds a random probing secure circuit from small base gadgets achieving a random probing expandability property. We instantiate this compiler with small gadgets for which we verify the expected properties directly from our automatic tool. Our construction can tolerate a leakage probability up to 2^−8, against 2^−25 for the previous construction, with a better asymptotic complexity.

2019

ASIACRYPT

On Kilian’s Randomization of Multilinear Map Encodings
Abstract

Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian’s randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian’s randomization after encoding, the complexity of the best attacks is significantly increased for CLT13 multilinear maps. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude.As an application, we describe the first concrete implementation of multiparty non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange that is resistant against known attacks, based on CLT13 multilinear maps. For
$$N=4$$
users and a medium level of security, our implementation requires 18 GB of public parameters, and a few minutes for the derivation of a shared key.

2019

ASIACRYPT

Cryptanalysis of CLT13 Multilinear Maps with Independent Slots
Abstract

Many constructions based on multilinear maps require independent slots in the plaintext, so that multiple computations can be performed in parallel over the slots. Such constructions are usually based on CLT13 multilinear maps, since CLT13 inherently provides a composite encoding space, with a plaintext ring
$$\bigoplus _{i=1}^n \mathbb {Z}/g_i\mathbb {Z}$$
for small primes
$$g_i$$
’s. However, a vulnerability was identified at Crypto 2014 by Gentry, Lewko and Waters, with a lattice-based attack in dimension 2, and the authors have suggested a simple countermeasure. In this paper, we identify an attack based on higher dimension lattice reduction that breaks the author’s countermeasure for a wide range of parameters. Combined with the Cheon et al. attack from Eurocrypt 2015, this leads to the recovery of all the secret parameters of CLT13, assuming that low-level encodings of almost zero plaintexts are available. We show how to apply our attack against various constructions based on composite-order CLT13. For the [FRS17] construction, our attack enables to recover the secret CLT13 plaintext ring for a certain range of parameters; however, breaking the indistinguishability of the branching program remains an open problem.

2018

TCHES

High Order Masking of Look-up Tables with Common Shares
📺
Abstract

Masking is an effective countermeasure against side-channel attacks. In this paper, we improve the efficiency of the high-order masking of look-up tables countermeasure introduced at Eurocrypt 2014, based on a combination of three techniques, and still with a proof of security in the Ishai-Sahai-Wagner (ISW) probing model. The first technique consists in proving security under the stronger t-SNI definition, which enables to use n = t+1 shares instead of n = 2t+1 against t-th order attacks. The second technique consists in progressively incrementing the number of shares within the countermeasure, from a single share to n, thereby reducing the complexity of the countermeasure. The third technique consists in adapting the common shares approach introduced by Coron et al. at CHES 2016, so that half of a randomized look-up table can be pre-computed for multiple SBoxes. We show that our techniques perform well in practice. In theory, the combination of the three techniques should lead to a factor 10.7 improvement in efficiency, for a large number of shares. For a practical implementation with a reasonable number of shares, we get a 4.8 speed-up factor for AES.

2018

TCHES

Improved High-Order Conversion From Boolean to Arithmetic Masking
📺
Abstract

Masking is a very common countermeasure against side channel attacks. When combining Boolean and arithmetic masking, one must be able to convert between the two types of masking, and the conversion algorithm itself must be secure against side-channel attacks. An efficient high-order Boolean to arithmetic conversion scheme was recently described at CHES 2017, with complexity independent of the register size. In this paper we describe a simplified variant with fewer mask refreshing, and still with a proof of security in the ISW probing model. In practical implementations, our variant is roughly 25% faster.

2017

CHES

High-Order Conversion from Boolean to Arithmetic Masking
Abstract

Masking with random values is an effective countermeasure against side-channel attacks. For cryptographic algorithms combining arithmetic and Boolean masking, it is necessary to switch from arithmetic to Boolean masking and vice versa. Following a recent approach by Hutter and Tunstall, we describe a high-order Boolean to arithmetic conversion algorithm whose complexity is independent of the register size k. Our new algorithm is proven secure in the Ishai, Sahai and Wagner (ISW) framework for private circuits. In practice, for small orders, our new countermeasure is one order of magnitude faster than previous work.We also describe a 3rd-order attack against the 3rd-order Hutter-Tunstall algorithm, and a constant, 4th-order attack against the t-th order Hutter-Tunstall algorithms, for any
$$t \ge 4$$
.

2014

EPRINT

2013

JOFC

A Note on the Bivariate Coppersmith Theorem
Abstract

In 1997, Coppersmith proved a famous theorem for finding small roots of bivariate polynomials over ℤ, with important applications to cryptography.While it seems to have been overlooked until now, we found the proof of the most commonly cited version of this theorem to be incomplete. Filling in the gap requires technical manipulations which we carry out in this paper.

2012

EUROCRYPT

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.

2008

EPRINT

The Random Oracle Model and the Ideal Cipher Model are Equivalent
Abstract

The Random Oracle Model and the Ideal Cipher Model are two well known idealised models of computation for proving the security of cryptosystems. At Crypto 2005, Coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. The other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. In this paper we solve this open problem and show that the Feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. This contrasts with the classical Luby-Rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.

2005

EPRINT

Secure Delegation of Elliptic-Curve Pairing
Abstract

In this paper we describe a simple protocol for securely delegating
elliptic-curve pairings. A computationally limited device (typically
a smart-card) will delegate the computation of the pairing e(A,B) to a
more powerful device (for example a PC), in such a way that:
1. the powerful device learns nothing about the points being paired (A
and B), nor about the pairing?s result e(A,B),
2. and the limited device is able to detect when the powerful device is cheating.
We also describe more efficient variants of our protocol when one of
the points or both are already known, and further efficiency gains when constant points are used.

2004

PKC

2004

EPRINT

Cryptanalysis of a Provably Secure Cryptographic Hash Function
Abstract

We present a cryptanalysis of a provably secure cryptographic hash function proposed by Augot, Finiasz and Sendrier on eprint. Our attack is a variant of Wagner's generalized birthday attack. It is significantly faster than the attack considered by the authors, and it is practical for two of the three proposed parameters.

2004

EPRINT

Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Abstract

We address one of the most fundamental problems concerning the RSA
cryptosystem: does the knowledge of the RSA public and secret key-pair
(e,d) yield the factorization of N=pq in polynomial
time? It is well-known that there is a probabilistic
polynomial time algorithm that on input (N,e,d) outputs the
factors p and q. We present the first deterministic
polynomial time algorithm that factors N provided that e,d<N.
Our approach is an application of Coppersmith's technique for
finding small roots
of univariate modular polynomials.

2004

EPRINT

Externalized Fingerprint Matching
Abstract

The 9/11 tragedy triggered an increased interest in biometric
passports. According to several sources \cite{sp2}, the electronic
ID market is expected to increase by more than 50\% {\sl per
annum} over the three coming years, excluding China.
\smallskip
To cost-effectively address this foreseen explosion, a very
inexpensive memory card (phonecard-like card) capable of
performing fingerprint matching is paramount.\smallskip
This paper presents such a solution. The proposed protocol is
based on the following idea: the card stores the user's
fingerprint information to which random minutiae were added at
enrolment time (we denote this scrambled template by $t$). The
card also stores a binary string $w$ encoding which of the
minutiae in $t$ actually belong to the holder. When an
identification session starts, the terminal reads $t$ from the
card and, based upon the incoming scanner data, determines which
of the minutiae in $t$ are genuine. The terminal forms a candidate
$w'$ and sends it to the card. All the card needs to do is test
that the Hamming weight of $w \oplus w'$ is smaller than a
security threshold $d$. \smallskip
It follows that the card only needs to embark passive data storage
capabilities, one exclusive-or gate, a shift register, a counter
and a comparator (less than 40 logical gates).

2003

ASIACRYPT

2003

EPRINT

Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem
Abstract

We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Therefore, the scheme is not one-way. Our technique is a variant of the Berlekamp-Welsh algorithm.

2003

EPRINT

Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem
Abstract

At Eurocrypt 2003, Augot and Finiasz proposed a new public-key
encryption scheme based on the polynomial reconstruction problem. The scheme was subsequently broken by Coron,
who showed that given the public-key and a ciphertext, one could
recover the corresponding plaintext in polynomial time. Recently,
Augot, Finiasz and Loidreau published on the IACR eprint archive a
reparation of the cryptosystem. The reparation is based on
the trace operator, and is resistant against the previous attack.
However, we describe a new cryptanalysis of the repaired scheme.
Given the public-key and a ciphertext, we can still recover the
corresponding plaintext in polynomial time. Our technique is
a variant of the Berlekamp-Welsh algorithm, and works very
well in practice, as for the proposed parameters, we recover the
plaintext in less than 8 minutes on a single PC.

2002

EPRINT

Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages
Abstract

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

2002

EPRINT

Universal Padding Schemes for RSA
Abstract

A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.

2001

EPRINT

Optimal security proofs for PSS and other signature schemes
Abstract

The Probabilistic Signature Scheme (PSS) designed by Bellare and
Rogaway is a signature scheme provably secure against chosen
message attacks in the random oracle model, with a security level equivalent to RSA.
In this paper, we derive a new security proof for PSS in which
a much shorter random salt is used to achieve the same security
level, namely we show that $\log_2 q_{sig}$ bits suffice, where
$q_{sig}$ is the number of signature queries made by the attacker.
When PSS is used with message recovery, a better
bandwidth is obtained because longer messages can now be
recovered. Moreover, we show that this size is optimal: if less
than $\log_2 q_{sig}$ bits of random salt are used, PSS is still
provably secure but no security proof can be tight. This result
is based on a new technique which shows that other
signature schemes such as the Full Domain Hash scheme and
Gennaro-Halevi-Rabin's scheme have optimal security proofs.

#### Program Committees

- CHES 2019
- Crypto 2019
- Eurocrypt 2017
- Eurocrypt 2016
- PKC 2015
- CHES 2015
- Asiacrypt 2014
- CHES 2014
- Eurocrypt 2014
- PKC 2013
- CHES 2013
- Crypto 2013
- CHES 2012
- Eurocrypt 2012
- PKC 2012
- Crypto 2011
- CHES 2011
- PKC 2010
- CHES 2010
- Asiacrypt 2010
- Eurocrypt 2010
- PKC 2009
- Crypto 2009
- CHES 2009
- Crypto 2008
- CHES 2008
- Asiacrypt 2007
- CHES 2007
- CHES 2006
- Eurocrypt 2006
- PKC 2006
- Crypto 2005
- Eurocrypt 2004
- CHES 2003
- Crypto 2003
- CHES 2002
- CHES 2001

#### Coauthors

- Claude Barral (1)
- Alberto Battistello (1)
- Aurélie Bauer (1)
- Anja Becker (1)
- Sonia Belaïd (3)
- Luk Bettale (1)
- Jingguo Bi (2)
- Eric Brier (2)
- Julien Cathalo (1)
- Jung Hee Cheon (1)
- Benoît Chevallier-Mames (1)
- Christophe Clavier (3)
- Don Coppersmith (1)
- Nora Dabbous (1)
- Yevgeniy Dodis (2)
- Jean-Charles Faugère (3)
- Pierre-Alain Fouque (2)
- Craig Gentry (2)
- Benoît Gérard (2)
- Agnese Gini (1)
- Christophe Giraud (1)
- Louis Goubin (1)
- Aurélien Greuet (2)
- François Grieu (1)
- Johann Großschädl (2)
- Shai Halevi (3)
- Helena Handschuh (3)
- Thomas Holenstein (1)
- Thomas Icart (1)
- Antoine Joux (4)
- Marc Joye (5)
- Charanjit S. Jutla (1)
- Jean-Gabriel Kammerer (2)
- Jinsu Kim (1)
- Alexey Kirichenko (1)
- Ilya Kizhvatov (3)
- François Koeune (1)
- Robin Künzler (1)
- Moon Sung Lee (3)
- David Lefranc (1)
- Tancrède Lepoint (10)
- David A. Madore (1)
- Hemanta K. Maji (2)
- Cécile Malinaud (1)
- Avradip Mandal (4)
- Alexander May (2)
- Noel McCullagh (1)
- Eric Miles (2)
- David Naccache (21)
- Phong Q. Nguyen (2)
- Luca Notarnicola (1)
- Pascal Paillier (6)
- Jacques Patarin (3)
- Hilder V. L. Pereira (1)
- David Pointcheval (2)
- Guillaume Poupard (1)
- Emmanuel Prouff (9)
- Prashant Puniya (1)
- Hugues Randriam (1)
- Mariana Raykova (2)
- Guénaël Renault (3)
- Matthieu Rivain (5)
- Thomas Roche (2)
- Franck Rondepierre (1)
- Arnab Roy (1)
- Amit Sahai (2)
- Michael Scott (1)
- Yannick Seurin (4)
- Julien P. Stern (2)
- Abdul Rahman Taleb (1)
- Alexei Tchulkine (1)
- Stefano Tessaro (1)
- Mehdi Tibouchi (19)
- Christophe Tymen (2)
- Praveen Kumar Vadnala (2)
- Damien Vergnaud (1)
- Srinivas Vivek (1)
- Ralf-Philipp Weinmann (2)
- Aaram Yun (1)
- Rina Zeitoun (8)