## CryptoDB

### Antoine Joux

#### Affiliation: CryptoExperts and UPMC

#### Publications

**Year**

**Venue**

**Title**

2018

CRYPTO

A New Public-Key Cryptosystem via Mersenne Numbers
📺
Abstract

In this work, we propose a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number
$$p = 2^n - 1$$
p=2n-1, where n is a prime, a positive integer h, and two n-bit integers T, R, decide whether their exist n-bit integers F, G each of Hamming weight less than h such that
$$T = F\cdot R + G$$
T=F·R+G modulo p.

2018

ASIACRYPT

How to Securely Compute with Noisy Leakage in Quasilinear Complexity
Abstract

Since their introduction in the late 90’s, side-channel attacks have been considered as a major threat against cryptographic implementations. This threat has raised the need for formal leakage models in which the security of implementations can be proved. At Eurocrypt 2013, Prouff and Rivain introduced the noisy leakage model which has been argued to soundly capture the physical reality of power and electromagnetic leakages. In their work, they also provide the first formal security proof for a masking scheme in the noisy leakage model. However their work has two important limitations: (i) the security proof relies on the existence of a leak-free component, (ii) the tolerated amount of information in the leakage (aka leakage rate) is of O(1 / n) where n is the security parameter (i.e. the number of shares in the underlying masking scheme). The first limitation was nicely tackled by Duc, Dziembowski and Faust one year later (Eurocrypt 2014). Their main contribution was to show a security reduction from the noisy leakage model to the conceptually simpler random-probing model. They were then able to prove the security of the well-known Ishai-Sahai-Wagner scheme (Crypto 2003) in the noisy leakage model. The second limitation was addressed in a paper by Andrychowicz, Dziembowski and Faust (Eurocrypt 2016) which makes use of a construction due to Ajtai (STOC 2011) to achieve security in the strong adaptive probing model with a leakage rate of $$O(1/\log n)$$. The authors argue that their result can be translated into the noisy leakage model with a leakage rate of O(1) by using secret sharing based on algebraic geometric codes. In terms of complexity, the protected program scales from |P| arithmetic instructions to $$\tilde{O}(|P| \, n^2)$$. According to the authors, this $$\tilde{O}(n^2)$$ blow-up could be reduced to $$\tilde{O}(n)$$ using packed secret sharing but no details are provided. Moreover, such an improvement would only be possible for a program of width at least linear in n. The issue of designing an explicit scheme achieving $$\tilde{O}(n)$$ complexity blow-up for any arithmetic program is hence left open.In this paper, we tackle the above issue: we show how to securely compute in the presence of noisy leakage with a leakage rate $$\tilde{O}(1)$$ and complexity blow-up $$\tilde{O}(n)$$. Namely, we introduce a transform that turns any program P composed of arithmetic instructions on some filed $$\mathbb {F}$$ into a (functionally equivalent) program $$\varPi $$ composed of $$|\varPi | = O(|P| n \log n)$$ arithmetic instructions which can tolerate some (quasi-constant) amount of noisy leakage on its internal variables (while revealing negligible information). We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the random-probing model with leakage rate $$O(1/\log n)$$. Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a $$O(1/|\mathbb {F}|^2 \log n)$$ leakage rate. However, a straight application of this reduction is not satisfactory since our construction requires $$|\mathbb {F}| = O(n)$$. In order to bypass this issue (which is shared with the construction of Andrychowicz et al.), we provide a generic security reduction from the noisy leakage model at the logical-instruction level to the random-probing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate $$\tilde{O}(1)$$.

2015

EPRINT

2014

EUROCRYPT

2014

EUROCRYPT

2013

EUROCRYPT

2012

EUROCRYPT

2012

EUROCRYPT

2012

EUROCRYPT

2010

EPRINT

A variant of the F4 algorithm
Abstract

Algebraic cryptanalysis usually requires to find solutions of several similar polynomial systems. A standard tool to solve this problem consists of computing the Gröbner bases of the corresponding ideals, and Faugère's F4 and F5 are two well-known algorithms for this task.
In this paper, we present a new variant of the F4 algorithm which is well suited to algebraic attacks of cryptosystems since it is designed to compute Gröbner bases of a set of polynomial systems having the same shape. It is faster than F4 as it avoids all reductions to zero, but preserves its simplicity and its computation efficiency, thus competing with F5.

2010

EPRINT

New generic algorithms for hard knapsacks
Abstract

In this paper, we
study the complexity of solving hard knapsack problems, i.e.,
knapsacks with a density close to $1$ where lattice-based low
density attacks are not an option. For such knapsacks, the current
state-of-the-art is a 31-year old algorithm by Schroeppel and Shamir
which is based on birthday paradox techniques and yields a running
time of $\TildeOh(2^{n/2})$ for knapsacks of $n$ elements and uses
$\TildeOh(2^{n/4})$ storage. We propose here two new algorithms
which improve on this bound, finally lowering the running time down
to $\TildeOh (2^{0.3113\, n})$ for almost all knapsacks of density $1$.
We also demonstrate the practicality
of these algorithms with an implementation.

2010

EPRINT

Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on $E(\F_{q^5})$
Abstract

In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve defined over a small degree extension field $\F_{q^n}$. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when $\log q \leq c n^3$. In particular, we are able to successfully obtain relations on $E(\F_{p^5})$, whereas the more expensive computational complexity of Gaudry and Diem's initial algorithm makes it impractical in this case. An important ingredient of this result is a new variation of Faugère's Gröbner basis algorithm F4, which significantly speeds up the relation computation and might be of independent interest. As an application, we show how this index calculus leads to a practical example of an oracle-assisted resolution of the elliptic curve static Diffie-Hellman problem over a finite field on $130$ bits, which is faster than birthday-based discrete logarithm computations on the same curve.

2010

EPRINT

Pairing computation on curves with efficiently computable endomorphism and small embedding degree
Abstract

Scott uses an efficiently computable isomorphism
in order to optimize pairing computation on a particular class of curves with embedding degree 2. He pointed out that
pairing implementation becomes thus faster on these curves than on their supersingular equivalent, originally recommended by Boneh and Franklin for Identity Based Encryption.
We extend Scott's method to other classes of curves with small embedding degree and efficiently computable endomorphism.
In particular, we optimize pairing computation on a class of curves with embedding degree 4 and discriminant 1,
which are interesting for pairing based cryptography because they have a very efficient arithmetic.

2009

EPRINT

On the Security of Iterated Hashing based on Forgery-resistant Compression Functions
Abstract

In this paper we re-examine the security notions suggested for hash
functions, with an emphasis on the delicate notion of second
preimage resistance. We start by showing that, in the random oracle
model, both Merkle-Damgaard and HAIFA achieve second preimage resistance beyond
the birthday bound, and actually up to the level of known generic
attacks, hence demonstrating the optimality of HAIFA in this respect.
We then try to distill a more elementary requirement out of the
compression function to get some insight on the properties it should
have to guarantee the second preimage resistance of its
iteration. We show that if the (keyed) compression function is a
secure FIL-MAC then the Merkle-Damgaard mode of iteration (or HAIFA) still
maintains the same level of second preimage resistance. We conclude
by showing that this ``new'' assumption (or security notion)
implies the recently introduced
Preimage-Awareness while ensuring all other classical security
notions for hash functions.

2008

EPRINT

Another approach to pairing computation in Edwards coordinates
Abstract

The recent introduction of Edwards curves has significantly reduced
the cost of addition on elliptic curves. This paper presents new
explicit formulae for pairing implementation in Edwards coordinates.
We prove our method gives performances similar to those of Miller's
algorithm in Jacobian coordinates and is thus of cryptographic
interest when one chooses Edwards curve implementations of protocols
in elliptic curve cryptography. The method is faster than the recent
proposal of Das and Sarkar for computing pairings on supersingular
curves using Edwards coordinates.

2008

EPRINT

Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms
Abstract

This paper extends Joux-Naccache-Thom\'e's $e$-th root algorithm to the static Diffie-Hellman problem ({\sc sdhp}).
The new algorithm can be adapted to diverse finite fields by customizing it with an {\sc nfs}-like core or an {\sc ffs}-like
core.
In both cases, after a number of {\sc sdhp} oracle queries, the attacker builds-up the ability to solve new {\sc sdhp} instances {\sl unknown before the query phase}.
While sub-exponential, the algorithm is still significantly faster than all currently known {\sc dlp} and {\sc sdhp} resolution methods.
We explore the applicability of the technique to various cryptosystems.
The attacks were implemented in ${\mathbb F}_{2^{1025}}$ and also in ${\mathbb F}_{p}$, for a $516$-bit $p$.

2007

EPRINT

When e-th Roots Become Easier Than Factoring
Abstract

We show that computing $e$-th roots modulo $n$ is easier than
factoring $n$ with currently known methods, given subexponential
access to an oracle outputting the roots of numbers of the form
$x_i + c$.
Here $c$ is fixed and $x_i$ denotes small integers of the
attacker's choosing.
Several variants of the attack are presented, with varying
assumptions on the oracle, and goals ranging from selective to
universal forgeries. The computational complexity of the attack
is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant
situations, which matches the {\sl
special} number field sieve's ({\sc snfs}) complexity.
This sheds additional light on {\sc rsa}'s malleability in
general and on {\sc rsa}'s resistance to affine forgeries in
particular -- a problem known to be polynomial for $x_i >
\sqrt[3]{n}$, but for which no algorithm faster than factoring
was known before this work.

2006

EPRINT

Counting points on elliptic curves in medium characteristic
Abstract

In this paper, we revisit the problem of computing the kernel of a separable isogeny of degree $\ell$ between two elliptic curves
defined over a finite field $\GF{q}$ of characteristic $p$. We
describe an algorithm the asymptotic time complexity of which is
equal to $\SoftO(\ell^2(1+\ell/p)\log q)$ bit operations. This
algorithm is particularly useful when $\ell > p$ and as a
consequence, we obtain an improvement of the complexity of the SEA
point counting algorithm for small values of $p$. More precisely, we
obtain a heuristic time complexity $\SoftO(\log^{4} q)$ and a space
complexity $O(\log^{2} q)$, in the previously unfavorable case where
$p \simeq \log q$. Compared to the best previous algorithms, the
memory requirements of our SEA variation are smaller by a $\log^2 q$
factor.

2004

EPRINT

Cryptanalysis of a Provably Secure Cryptographic Hash Function
Abstract

We present a cryptanalysis of a provably secure cryptographic hash function proposed by Augot, Finiasz and Sendrier on eprint. Our attack is a variant of Wagner's generalized birthday attack. It is significantly faster than the attack considered by the authors, and it is practical for two of the three proposed parameters.

2003

CRYPTO

2003

JOFC

2002

FSE

2001

EPRINT

Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups
Abstract

In many cases, the security of a cryptographic scheme based on Diffie--Hellman does in fact rely on the hardness of the
Diffie--Hellman Decision problem. In this paper, we show that the
hardness of Decision Diffie--Hellman is a much stronger hypothesis than the hardness of the regular Diffie--Hellman problem. Indeed, we
describe a reasonably looking cryptographic group where Decision
Diffie--Hellman is easy while Diffie--Hellman is equivalent to a --
presumably hard -- Discrete Logarithm Problem. This shows that care
should be taken when dealing with Decision Diffie--Hellman, since its
security cannot be taken for granted.

2001

EPRINT

On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit - A New Construction
Abstract

In this paper, we study the security of randomized CBC-MACs and propose a new construction that resists birthday paradox attacks and provably reaches full security. The size of the MAC tags in this construction is optimal, i.e., exactly twice the size of the block cipher. Up to a constant, the security of the proposed randomized CBC-MAC using an n-bit block cipher is the same as the security of the usual encrypted CBC-MAC using a 2n-bit block cipher. Moreover, this construction adds a negligible computational overhead compared to the cost of a plain, non-randomized CBC-MAC. We give a full standard proof of our construction using one pass of a block cipher with 2n-bit keys but there also is a proof for n-bit keys block ciphers in the ideal cipher model.

#### Program Committees

- Crypto 2020
- Asiacrypt 2016
- PKC 2013
- FSE 2012
- Crypto 2012
- Asiacrypt 2012
- Asiacrypt 2011
- FSE 2011
- Asiacrypt 2010
- FSE 2010
- Eurocrypt 2010
- Eurocrypt 2009
- FSE 2008
- Eurocrypt 2008
- Crypto 2007
- FSE 2007
- Asiacrypt 2006
- FSE 2006
- Eurocrypt 2006
- FSE 2005
- Crypto 2005
- Eurocrypt 2004
- Crypto 2003
- PKC 2002
- Eurocrypt 2002

#### Coauthors

- Divesh Aggarwal (1)
- Razvan Barbulescu (1)
- Aurélie Bauer (1)
- Anja Becker (3)
- Eli Biham (2)
- Dan Boneh (1)
- Charles Bouillaguet (1)
- Patrick Carribault (1)
- Guilhem Castagnos (1)
- Florent Chabaud (1)
- Yeow Meng Chee (1)
- Rafi Chen (2)
- Philippe Chose (1)
- Jean-Sébastien Coron (4)
- Orr Dunkelman (1)
- Jean-Charles Faugère (2)
- Pierre-Alain Fouque (2)
- Nicolas Gama (1)
- Pierrick Gaudry (1)
- Henri Gilbert (1)
- Dahmun Goudarzi (1)
- Louis Granboulan (2)
- Helena Handschuh (1)
- Nick Howgrave-Graham (2)
- Louise Huot (1)
- Sorina Ionica (2)
- William Jalby (1)
- Éliane Jaulmes (5)
- Ilya Kizhvatov (1)
- Sébastien Kunz-Jacques (1)
- Fabien Laguillaumie (1)
- Christophe Lemuet (1)
- Reynald Lercier (4)
- Stefan Lucks (1)
- Avradip Mandal (1)
- Gwenaëlle Martinet (1)
- Chrysanthi Mavromati (1)
- Alexander May (1)
- Marcel Medwed (1)
- Alexander Meurer (1)
- Michel Mitton (1)
- Frédéric Muller (4)
- David Naccache (5)
- Kim Nguyen (2)
- Phong Q. Nguyen (2)
- Pascal Paillier (1)
- Thomas Peyrin (1)
- Cécile Pierrot (2)
- Guillaume Poupard (1)
- Anupam Prakash (1)
- Jean-René Reinhard (1)
- Guénaël Renault (1)
- Pierre-Michel Ricordel (1)
- Matthieu Rivain (1)
- Miklos Santha (1)
- Nigel P. Smart (1)
- François-Xavier Standaert (1)
- Jacques Stern (5)
- Emmanuel Thomé (4)
- Mehdi Tibouchi (1)
- Frédéric Valette (3)
- Serge Vaudenay (1)
- Frederik Vercauteren (1)
- Vanessa Vitse (4)