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

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.

2022

CRYPTO

Shorter Hash-and-Sign Lattice-Based Signatures
📺
Abstract

Lattice-based digital signature schemes following the hash-and-sign design paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer an attractive level of efficiency, particularly when instantiated with structured compact trapdoors. In particular, NIST postquantum finalist Falcon is both quite fast for signing and verification and quite compact: NIST notes that it has the smallest bandwidth (as measured in combined size of public key and signature) of all round 2 digital signature candidates. Nevertheless, while Falcon--512, for instance, compares favorably to ECDSA--384 in terms of speed, its signatures are well over 10 times larger. For applications that store large number of signatures, or that require signatures to fit in prescribed packet sizes, this can be a critical limitation.
In this paper, we explore several approaches to further improve the size of hash-and-sign lattice-based signatures, particularly instantiated over NTRU lattices like Falcon and its recent variant Mitaka. In particular, while GPV signatures are usually obtained by sampling lattice points according to some *spherical* discrete Gaussian distribution, we show that it can be beneficial to sample instead according to a suitably chosen *ellipsoidal* discrete Gaussian: this is because only half of the sampled Gaussian vector is actually output as the signature, while the other half is recovered during verification. Making the half that actually occurs in signatures shorter reduces signature size at essentially no security loss (in a suitable range of parameters). Similarly, we show that reducing the modulus $q$ with respect to which signatures are computed can improve signature size as well as verification key size almost ``for free''; this is particularly true for constructions like Falcon and Mitaka that do not make substantial use of NTT-based multiplication (and rely instead on transcendental FFT). Finally, we show that the Gaussian vectors in signatures can be represented in a more compact way with appropriate coding-theoretic techniques, improving signature size by an additional 7 to 14%. All in all, we manage to reduce the size of, e.g., Falcon signatures by 30--40% at the cost of only 4--6 bits of Core-SVP security.

2022

CRYPTO

MuSig-L: Lattice-Based Multi-Signature With Single-Round Online Phase
📺
Abstract

Multi-signatures are protocols that allow a group of signers to jointly produce a single signature on the same message. In recent years, a number of practical multi-signature schemes have been proposed in the discrete-log setting, such as MuSigT (CRYPTO'21) and DWMS (CRYPTO'21).
The main technical challenge in constructing a multi-signature scheme is to achieve a set of several desirable properties, such as (1) security in the plain public-key (PPK) model, (2) concurrent security, (3) low online round complexity, and (4) key aggregation. However, previous lattice-based, post-quantum counterparts to Schnorr multi-signatures fail to satisfy these properties.
In this paper, we introduce MuSigL, a lattice-based multi-signature scheme simultaneously achieving these design goals for the first time.
Unlike the recent, round-efficient proposal of Damgård et al. (PKC'21), which had to rely on lattice-based trapdoor commitments, we do not require any additional primitive in the protocol, while being able to prove security from the standard module-SIS and LWE assumptions.
The resulting output signature of our scheme therefore looks closer to the usual Fiat--Shamir-with-abort signatures.

2022

ASIACRYPT

SwiftEC: Shallue--van de Woestijne Indifferentiable Function to Elliptic Curves
Abstract

Hashing arbitrary values to points on an elliptic curve is a required
step in many cryptographic constructions, and a number of techniques have
been proposed to do so over the years. One of the first ones was due to
Shallue and van de Woestijne (ANTS-VII), and it had the interesting
property of applying to essentially all elliptic curves over finite
fields. It did not, however, have the desirable property of being
*indifferentiable from a random oracle* when composed with a random
oracle to the base field.
Various approaches have since been considered to overcome this
limitation, starting with the foundational work of Brier et al. (CRYPTO
2011). For example, if f: F_q→E(F_q) is the Shallue--van de
Woestijne (SW) map and H, H' are *two* independent random oracles,
we now know that m↦f(H(m))+f(H'(m)) is
indifferentiable from a random oracle. Unfortunately, this approach has
the drawback of being twice as expensive to compute than the
straightforward, but not indifferentiable, m↦f(H(m)).
Most other solutions so far have had the same issue: they are at least as
costly as two base field exponentiations, whereas plain encoding maps
like f cost only one exponentiation. Recently, Koshelev (DCC 2022)
provided the first construction of indifferentiable hashing at the cost
of one exponentiation, but only for a very specific class of curves
(some of those with j-invariant 0), and using techniques that are unlikely to
apply more broadly.
In this work, we revisit this long-standing open problem, and observe
that the SW map actually fits in a one-parameter family (f_u)_{u∈F_q}
of encodings, such that for independent random oracles H, H',
F: m↦f_{H'(m)}(H(m)) is indifferentiable. Moreover, on a
very large class of curves (essentially those that are either of odd
order or of order divisible by 4), the one-parameter family admits a
rational parametrization, which lets us compute F at almost the same
cost as small f, and finally achieve indifferentiable hashing to most
curves with a single exponentiation.
Our new approach also yields an improved variant of the Elligator Squared
technique of Tibouchi (FC 2014) that represents points of arbitrary
elliptic curves as close-to-uniform random strings.

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

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 (6)
- Diego F. Aranha (1)
- Gilles Barthe (3)
- Sonia Belaïd (1)
- Jonathan Bootle (1)
- Cecilia Boschini (1)
- Eric Brier (2)
- Jorge Chavez-Saab (1)
- 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)
- Francisco Rodríguez-Henríquez (1)
- Mélissa Rossi (2)
- Amit Sahai (1)
- Andre Scedrov (1)
- Benedikt Schmidt (1)
- Chao Sun (1)
- Akira Takahashi (4)
- Praveen Kumar Vadnala (1)
- Alexandre Wallet (3)
- Ralf-Philipp Weinmann (2)
- Yang Yu (3)
- Aaram Yun (1)
- Jean-Christophe Zapalowicz (3)