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

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.

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

EPRINT

2015

PKC

2014

EPRINT

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

2010

EPRINT

Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves
Abstract

Let E be a non-supersingular elliptic curve over a finite field F_q.
At CRYPTO 2009, Icart introduced a deterministic function
F_q->E(F_q) which can be computed efficiently, and allowed him and
Coron to define well-behaved hash functions with
values in E(F_q). Some properties of this function rely on a conjecture
which was left as an open problem in Icart's paper. We prove this
conjecture as well as analogues for other hash functions.
See also Farahashi, Shparlinski and Voloch, _On Hashing into Elliptic Curves_, for independent results of a similar form.

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.

2010

EPRINT

Deterministic Encoding and Hashing to Odd Hyperelliptic Curves
Abstract

In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves.
Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well as injective maps to J(F_q) which can be used to encode scalars for such applications as ElGamal encryption.
The new encoding is already interesting in the genus 1 case, where it provides a well-behaved encoding to Joux's supersingular elliptic curves.

2010

EPRINT

Huff's Model for Elliptic Curves
Abstract

This paper revisits a model for elliptic curves over Q introduced by Huff in 1948 to study a diophantine problem. Huff's model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of Z/4Z×Z/2Z is birationally equivalent to a Huff curve over the original field.
This paper extends and generalizes Huff's model. It presents fast explicit formulas for point addition and doubling on Huff curves. It also addresses the problem of the efficient evaluation of pairings over Huff curves. Remarkably, the formulas we obtain feature some useful properties, including completeness and independence of the curve parameters.

#### Program Committees

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

#### Coauthors

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