## CryptoDB

### Jean-Sébastien Coron

#### Publications

Year
Venue
Title
2022
TCHES
Masking is the main countermeasure against side-channel attacks on embedded devices. For cryptographic algorithms that combine Boolean and arithmetic masking, one must therefore convert between the two types of masking, without leaking additional information to the attacker. In this paper we describe a new high-order conversion algorithm between Boolean and arithmetic masking, based on table recomputation, and provably secure in the ISW probing model. We show that our technique is particularly efficient for masking structured LWE encryption schemes such as Kyber and Saber. In particular, for Kyber IND-CPA decryption, we obtain an order of magnitude improvement compared to existing techniques.
2022
TCHES
The main protection against side-channel attacks consists in computing every function with multiple shares via the masking countermeasure. For IND-CCA secure lattice-based encryption schemes, the masking of the decryption algorithm requires the high-order computation of a polynomial comparison. In this paper, we describe and evaluate a number of different techniques for such high-order comparison, always with a security proof in the ISW probing model. As an application, we describe the full high-order masking of the NIST standard Kyber, with a concrete implementation on ARM Cortex M architecture, and a t-test evaluation.
2021
CRYPTO
In this paper we describe the first improvement of the wire shuffling countermeasure against side-channel attacks described by Ishai, Sahai and Wagner at Crypto 2003. More precisely, we show how to get worst case statistical security against t probes with running time O(t) instead of O(t log t); our construction is also much simpler. Recall that the classical masking countermeasure achieves perfect security but with running time O(t^2). We also describe a practical implementation for AES that outperforms the masking countermeasure for t ≥ 6 000.
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 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.
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.
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
FSE
2015
CRYPTO
2015
CRYPTO
2015
CHES
2014
EUROCRYPT
2014
PKC
2014
PKC
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
CRYPTO
2010
CHES
2009
ASIACRYPT
2009
CHES
2009
CHES
2009
CRYPTO
2008
JOFC
2008
CHES
2008
CRYPTO
2007
CHES
2007
CHES
2007
CRYPTO
2007
JOFC
2005
CHES
2005
CRYPTO
2005
PKC
2004
EUROCRYPT
2004
PKC
2003
ASIACRYPT
2003
CHES
2002
CRYPTO
2002
CRYPTO
2002
EUROCRYPT
2002
PKC
2001
CRYPTO
2000
ASIACRYPT
2000
CHES
2000
CHES
2000
CRYPTO
2000
EUROCRYPT
2000
EUROCRYPT
1999
ASIACRYPT
1999
CHES
1999
CRYPTO
1999
PKC
1999
PKC

#### Program Committees

CHES 2022
Eurocrypt 2021
Crypto 2019
CHES 2019
Eurocrypt 2017 (Program chair)
Eurocrypt 2016 (Program chair)
CHES 2015
PKC 2015
CHES 2014
Eurocrypt 2014
Asiacrypt 2014
CHES 2013 (Program chair)
PKC 2013
Crypto 2013
CHES 2012
PKC 2012
Eurocrypt 2012
CHES 2011
Crypto 2011
CHES 2010
PKC 2010
Asiacrypt 2010
Eurocrypt 2010
Crypto 2009
PKC 2009
CHES 2009
Crypto 2008
CHES 2008
CHES 2007
Asiacrypt 2007
CHES 2006
PKC 2006
Eurocrypt 2006
Crypto 2005
Eurocrypt 2004
CHES 2003
Crypto 2003
CHES 2002
CHES 2001

#### Coauthors

Alberto Battistello (1)
Anja Becker (1)
Sonia Belaïd (2)
Luk Bettale (1)
Jingguo Bi (1)
Eric Brier (2)
Julien Cathalo (1)
Jung Hee Cheon (1)
Christophe Clavier (3)
Don Coppersmith (1)
Nora Dabbous (1)
Yevgeniy Dodis (2)
Jean-Charles Faugère (1)
Pierre-Alain Fouque (1)
Craig Gentry (1)
Benoît Gérard (1)
François 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 (2)
Helena Handschuh (2)
Thomas Holenstein (1)
Thomas Icart (1)
Antoine Joux (3)
Marc Joye (3)
Charanjit S. Jutla (1)
Jean-Gabriel Kammerer (1)
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 (7)
Hemanta K. Maji (1)
Cécile Malinaud (1)
Alexander May (1)
Eric Miles (1)
Simon Montoya (2)
David Naccache (17)
Phong Q. Nguyen (1)
Luca Notarnicola (1)
Pascal Paillier (4)
Jacques Patarin (2)
Hilder V. L. Pereira (1)
David Pointcheval (1)
Guillaume Poupard (1)
Emmanuel Prouff (7)
Prashant Puniya (1)
Hugues Randriam (1)
Mariana Raykova (1)
Guénaël Renault (1)
Matthieu Rivain (4)
Thomas Roche (1)
Franck Rondepierre (1)
Arnab Roy (1)
Amit Sahai (1)
Yannick Seurin (3)
Lorenzo Spignoli (1)
Julien P. Stern (2)
Abdul Rahman Taleb (1)
Alexei Tchulkine (1)
Stefano Tessaro (1)
Mehdi Tibouchi (15)
Christophe Tymen (1)