## CryptoDB

### Jean-Sébastien Coron

#### Publications

**Year**

**Venue**

**Title**

2022

TCHES

High-order Table-based Conversion Algorithms and Masking Lattice-based Encryption
Abstract

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

High-order Polynomial Comparison and Masking Lattice-based Encryption
Abstract

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

Secure Wire Shuffling in the Probing Model
📺
Abstract

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

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

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.

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.

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$$
.

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

2004

PKC

2003

ASIACRYPT

#### 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)
- David A. Madore (1)
- Hemanta K. Maji (1)
- Cécile Malinaud (1)
- Avradip Mandal (4)
- 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)
- Praveen Kumar Vadnala (2)
- Srinivas Vivek (1)
- Ralf-Philipp Weinmann (2)
- Aaram Yun (1)
- Rina Zeitoun (8)