## CryptoDB

### Jean-Sébastien Coron

#### Publications

Year
Venue
Title
2020
EUROCRYPT
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
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
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
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
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
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
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
PKC
2017
CHES
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$ .
2016
CRYPTO
2016
CHES
2016
CHES
2016
JOFC
2016
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
FSE
2015
CRYPTO
2015
CRYPTO
2015
CHES
2014
EUROCRYPT
2014
PKC
2014
PKC
2014
EPRINT
2014
EPRINT
2014
CHES
2014
CHES
2013
CRYPTO
2013
EUROCRYPT
2013
FSE
2013
JOFC
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
2011
PKC
2011
CRYPTO
2011
EUROCRYPT
2010
TCC
2010
EPRINT
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
CRYPTO
2010
CHES
2009
ASIACRYPT
2009
CHES
2009
CHES
2009
CRYPTO
2008
JOFC
2008
EPRINT
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.
2008
CHES
2008
CRYPTO
2007
CHES
2007
CHES
2007
CRYPTO
2007
JOFC
2005
CHES
2005
CRYPTO
2005
PKC
2005
EPRINT
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
EUROCRYPT
2004
PKC
2004
EPRINT
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
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
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
CHES
2003
EPRINT
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
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
CRYPTO
2002
CRYPTO
2002
EUROCRYPT
2002
PKC
2002
EPRINT
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
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
CRYPTO
2001
EPRINT
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.
2000
ASIACRYPT
2000
CHES
2000
CHES
2000
CRYPTO
2000
EUROCRYPT
2000
EUROCRYPT
1999
ASIACRYPT
1999
CHES
1999
CRYPTO
1999
PKC
1999
PKC

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)
Hemanta K. Maji (2)
Cécile Malinaud (1)
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)