## CryptoDB

### Mehdi Tibouchi

#### Affiliation: NTT Laboratories, Japan

#### Publications

**Year**

**Venue**

**Title**

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 2019
- Eurocrypt 2019
- CHES 2019
- Asiacrypt 2018
- PKC 2018
- Crypto 2017
- Asiacrypt 2017
- CHES 2017
- Asiacrypt 2016
- CHES 2016
- PKC 2016
- Crypto 2016
- CHES 2015
- Asiacrypt 2015
- CHES 2014
- CHES 2013

#### Coauthors

- Michel Abdalla (2)
- Masayuki Abe (7)
- 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)
- Claire Delaplace (1)
- François Dupressoir (2)
- Thomas Espitau (2)
- Edvard Fagerholm (2)
- Dario Fiore (2)
- Pierre-Alain Fouque (12)
- Craig Gentry (3)
- Benoît Gérard (1)
- Benjamin Grégoire (2)
- Benjamin Grégoire (1)
- Johann Großschädl (1)
- Jens Groth (4)
- Nicolas Guillermin (1)
- Shai Halevi (3)
- Thomas Icart (1)
- Antoine Joux (1)
- Marc Joye (1)
- Jean-Gabriel Kammerer (1)
- Jinsu Kim (1)
- Alexey Kirichenko (1)
- Markulf Kohlweiss (2)
- 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 (6)
- Chen Qian (1)
- Hugues Randriam (1)
- Mariana Raykova (2)
- Mélissa Rossi (1)
- Amit Sahai (3)
- Andre Scedrov (2)
- Benedikt Schmidt (2)
- Akira Takahashi (1)
- Praveen Kumar Vadnala (1)
- Damien Vergnaud (2)
- Ralf-Philipp Weinmann (2)
- Aaram Yun (1)
- Jean-Christophe Zapalowicz (5)