## CryptoDB

### Mehdi Tibouchi

#### Publications

**Year**

**Venue**

**Title**

2022

TCHES

Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
Abstract

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature
schemes) with partially known nonces, originally due to Howgrave-Graham
and Smart, has been at the core of many concrete cryptanalytic works,
side-channel based or otherwise, in the past 20 years. The attack itself
has seen limited development, however: improved analyses have been
carried out, and the use of stronger lattice reduction algorithms has
pushed the range of practically vulnerable parameters further, but the
lattice construction based on the signatures and known nonce bits remain
the same.
In this paper, we propose a simple idea to improve the attack based on
the same data in exchange for additional computation: carry out an
exhaustive search on some bits of the secret key. This turns the problem
from a single bounded distance decoding (BDD) instance in a certain
lattice to multiple BDD instances in a fixed lattice of larger volume but
with the same bound (making the BDD problem substantially easier).
Furthermore, the fact that the lattice is fixed lets us use
batch/preprocessing variants of BDD solvers that are far more efficient
than repeated lattice reductions on non-preprocessed lattices of the same
size. As a result, our analysis suggests that our technique is
competitive or outperforms the state of the art for parameter ranges
corresponding to the limit of what is achievable using lattice attacks so
far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit
groups).
We also show that variants of this idea can also be applied to bits of
the nonces (leading to a similar improvement) or to filtering signature
data (leading to a data-time trade-off for the lattice attack). Finally,
we use our technique to obtain an improved exploitation of the TPM–FAIL
dataset similar to what was achieved in the Minerva attack.

2022

EUROCRYPT

Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon
Abstract

This work describes the Mitaka signature scheme: a new hash-and-sign
signature scheme over NTRU lattices which can be seen as a variant of
NIST finalist Falcon. It achieves comparable efficiency but is
considerably simpler, online/offline, and easier to parallelize and
protect against side-channels, thus offering significant advantages from
an implementation standpoint. It is also much more versatile in terms of
parameter selection.
We obtain this signature scheme by replacing the FFO lattice Gaussian
sampler in Falcon by the “hybrid” sampler of Ducas and Prest, for
which we carry out a detailed and corrected security analysis. In
principle, such a change can result in a substantial security loss, but
we show that this loss can be largely mitigated using new techniques in
key generation that allow us to construct much higher quality lattice
trapdoors for the hybrid sampler relatively cheaply. This new approach
can also be instantiated on a wide variety of base fields, in contrast
with Falcon's restriction to power-of-two cyclotomics.
We also introduce a new lattice Gaussian sampler with the same quality
and efficiency, but which is moreover compatible with the integral matrix
Gram root technique of Ducas et al., allowing us to avoid floating point
arithmetic. This makes it possible to realize the same signature
scheme as Mitaka efficiently on platforms with poor support for
floating point numbers.
Finally, we describe a provably secure masking of Mitaka. More precisely,
we introduce novel gadgets that allow provable masking at any order at much
lower cost than previous masking techniques for Gaussian sampling-based
signature schemes, for cheap and dependable side-channel protection.

2021

PKC

Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattice
📺
Abstract

Although they have been studied for a long time, distributed signature
protocols have garnered renewed interest in recent years in view of novel
applications to topics like blockchains. Most recent works have focused
on distributed versions of ECDSA or variants of Schnorr signatures,
however, and in particular, little attention has been given to
constructions based on post-quantum secure assumptions like the hardness
of lattice problems. A few lattice-based threshold signature and
multi-signature schemes have been proposed in the literature, but they
either rely on hash-and-sign lattice signatures (which tend to be
comparatively inefficient), use expensive generic transformations, or
only come with incomplete security proofs.
In this paper, we construct several lattice-based distributed signing
protocols with low round complexity following the Fiat--Shamir with
Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed
variants of the fast Dilithium-G signature scheme and the full security proof can
be made assuming the hardness of module SIS and LWE problems. A key step to achieving
security (unexplained in some earlier papers) is to prevent the leakage
that can occur when parties abort after their first message---which can
inevitably happen in the Fiat--Shamir with Aborts setting. We manage to
do so using homomorphic commitments.
Exploiting the similarities between FSwA and Schnorr-style signatures,
our approach makes the most of observations from recent advancements in the
discrete log setting, such as Drijvers et al.'s seminal work on two-round multi-signatures (S&P 2019).
In particular, we observe that the use of commitment not only resolves the
subtle issue with aborts, but also makes it possible to realize secure two-round
n-out-of-n distributed signing and multi-signature
in the plain public key model, by equipping the commitment with a trapdoor feature.
The construction of suitable trapdoor commitment from
lattices is a side contribution of this paper.

2021

TCHES

Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
Abstract

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but the lattice construction based on the signatures and known nonce bits remain the same.In this paper, we propose a new idea to improve the attack based on the same data in exchange for additional computation: carry out an exhaustive search on some bits of the secret key. This turns the problem from a single bounded distance decoding (BDD) instance in a certain lattice to multiple BDD instances in a fixed lattice of larger volume but with the same bound (making the BDD problem substantially easier). Furthermore, the fact that the lattice is fixed lets us use batch/preprocessing variants of BDD solvers that are far more efficient than repeated lattice reductions on non-preprocessed lattices of the same size. As a result, our analysis suggests that our technique is competitive or outperforms the state of the art for parameter ranges corresponding to the limit of what is achievable using lattice attacks so far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit groups).We also show that variants of this idea can also be applied to bits of the nonces (leading to a similar improvement) or to filtering signature data (leading to a data-time trade-off for the lattice attack). Finally, we use our technique to obtain an improved exploitation of the TPM–FAIL dataset similar to what was achieved in the Minerva attack.

2020

EUROCRYPT

Key Recovery from Gram--Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices
📺
Abstract

In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold.
First, we identify a specific source of side-channel leakage in most implementations of those schemes, namely, the one-dimensional Gaussian sampling steps within lattice Gaussian sampling. It turns out that the implementations of these steps often leak the Gram--Schmidt norms of the secret lattice basis.
Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram--Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field.
Third, we concretely demonstrate the side-channel attack against DLP (but not Falcon due to the different structures of the two schemes). The challenge is that timing information only provides an approximation of the Gram--Schmidt norms, so our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximate values. Experimentally, we show that around $2^{35}$ DLP traces are enough to reconstruct the entire key with good probability.

2019

JOFC

Efficient Fully Structure-Preserving Signatures and Shrinking Commitments
Abstract

In structure-preserving signatures, public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys are group elements. This strong property allows efficient non-interactive proofs of knowledge of the secret key, which is useful in designing cryptographic protocols under simulation-based security where online extraction of the secret key is needed. We present efficient constructions under simple standard assumptions and pursue even more efficient constructions with the extra property of randomizability based on the generic bilinear group model. An essential building block for our efficient standard model construction is a shrinking structure-preserving trapdoor commitment scheme, which is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result that structure-preserving commitments cannot be shrinking. We argue that a relaxed binding property lets us circumvent the impossibility while still retaining the usefulness of the primitive in important applications as mentioned above.

2018

TCHES

New Bleichenbacher Records: Fault Attacks on qDSA Signatures
Abstract

In this paper, we optimize Bleichenbacher’s statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher’s attack suffered from very large memory consumption during the so-called “range reduction” phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel–Shamir algorithm for knapsacks, we manage to overcome the memory barrier of previous work while maintaining a practical level of efficiency in terms of time complexity.As a separate contribution, we present new fault attacks against the qDSA signature scheme of Renes and Smith (ASIACRYPT 2017) when instantiated over the Curve25519 Montgomery curve, and we validate some of them on the AVR microcontroller implementation of qDSA using actual fault experiments on the ChipWhisperer-Lite evaluation board. These fault attacks enable an adversary to generate signatures with 2 or 3 bits of the nonces known.Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher’s attack to these faulty signatures. Using a hybrid parallelization model relying on both shared and distributed memory, we achieve a very efficient implementation of our highly scalable range reduction algorithm. This allows us to complete Bleichenbacher’s attack in the 252-bit prime order subgroup of Curve25519 within a reasonable time frame and using relatively modest computational resources both for 3-bit nonce exposure and for the much harder case of 2-bit nonce exposure. Both of these computations, and particularly the latter, set new records in the implementation of Bleichenbacher’s attack.

2018

ASIACRYPT

LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
Abstract

This paper is devoted to analyzing the variant of Regev’s learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector $$\mathbf {s}\in \mathbb {Z}^n$$ given polynomially many samples of the form $$(\mathbf {a},\langle \mathbf {a},\mathbf {s}\rangle + e)\in \mathbb {Z}^{n+1}$$ where $$\mathbf { a}$$ and e follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be solved efficiently as long as the variance of e is not superpolynomially larger than that of $$\mathbf { a}$$. We also provide almost tight bounds on the number of samples needed to recover $$\mathbf {s}$$.Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to $${\approx }7\%$$ in the CCS paper), and is also considerably faster.

2016

PKC

2015

PKC

2014

ASIACRYPT

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

#### Program Committees

- Asiacrypt 2021 (Program chair)
- CHES 2021
- Asiacrypt 2020
- CHES 2020 (Program chair)
- Asiacrypt 2019
- CHES 2019
- Eurocrypt 2019
- PKC 2018
- Asiacrypt 2018
- Asiacrypt 2017
- CHES 2017
- Crypto 2017
- CHES 2016
- PKC 2016
- Asiacrypt 2016
- Crypto 2016
- Asiacrypt 2015
- CHES 2015
- CHES 2014
- CHES 2013

#### Coauthors

- Michel Abdalla (2)
- Masayuki Abe (7)
- Diego F. Aranha (1)
- Gilles Barthe (3)
- Sonia Belaïd (1)
- Jonathan Bootle (1)
- Eric Brier (2)
- Jung Hee Cheon (1)
- Jean-Sébastien Coron (15)
- Ivan Damgård (1)
- Claire Delaplace (1)
- François Dupressoir (1)
- Thomas Espitau (5)
- Edvard Fagerholm (1)
- Dario Fiore (1)
- Pierre-Alain Fouque (10)
- Craig Gentry (1)
- Benoît Gérard (1)
- François Gérard (1)
- Benjamin Grégoire (1)
- Benjamin Grégoire (1)
- Johann Großschädl (1)
- Jens Groth (3)
- Nicolas Guillermin (1)
- Shai Halevi (1)
- Thomas Icart (1)
- Antoine Joux (1)
- Jean-Gabriel Kammerer (1)
- Jinsu Kim (1)
- Paul Kirchner (1)
- Alexey Kirichenko (1)
- Markulf Kohlweiss (2)
- Moon Sung Lee (4)
- Tancrède Lepoint (8)
- Delphine Leresteux (1)
- Vadim Lyubashevsky (2)
- David A. Madore (1)
- Hemanta K. Maji (1)
- Avradip Mandal (2)
- Eric Miles (1)
- David Naccache (6)
- Samuel Neves (1)
- Phong Q. Nguyen (1)
- Miyako Ohkubo (4)
- Claudio Orlandi (1)
- Hugues Randriam (1)
- Mariana Raykova (1)
- Mélissa Rossi (2)
- Amit Sahai (1)
- Andre Scedrov (1)
- Benedikt Schmidt (1)
- Chao Sun (2)
- Akira Takahashi (3)
- Praveen Kumar Vadnala (1)
- Alexandre Wallet (2)
- Ralf-Philipp Weinmann (2)
- Yang Yu (2)
- Aaram Yun (1)
- Jean-Christophe Zapalowicz (3)