International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Antoine Joux

Affiliation: CryptoExperts and UPMC

Publications

Year
Venue
Title
2018
CRYPTO
A New Public-Key Cryptosystem via Mersenne Numbers 📺
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
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
JOFC
2015
EPRINT
2015
EPRINT
2015
PKC
2014
EUROCRYPT
2014
EUROCRYPT
2014
ASIACRYPT
2014
ASIACRYPT
2013
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2012
CHES
2011
PKC
2011
EUROCRYPT
2011
FSE
2010
EPRINT
A variant of the F4 algorithm
Antoine Joux Vanessa Vitse
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
Nick Howgrave-Graham Antoine Joux
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})$
Antoine Joux Vanessa Vitse
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
Sorina Ionica Antoine Joux
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.
2010
EUROCRYPT
2009
ASIACRYPT
2009
ASIACRYPT
2009
CHES
2009
EPRINT
On the Security of Iterated Hashing based on Forgery-resistant Compression Functions
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
Sorina Ionica Antoine Joux
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
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
ASIACRYPT
2007
CRYPTO
2007
EUROCRYPT
2007
FSE
2007
EPRINT
When e-th Roots Become Easier Than Factoring
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
CRYPTO
2006
CRYPTO
2006
EUROCRYPT
2006
FSE
2006
EPRINT
Counting points on elliptic curves in medium characteristic
Antoine Joux Reynald Lercier
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.
2005
EUROCRYPT
2005
FSE
2005
PKC
2004
CRYPTO
2004
EPRINT
Cryptanalysis of a Provably Secure Cryptographic Hash Function
Jean-Sébastien Coron Antoine Joux
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.
2004
JOFC
2003
CRYPTO
2003
EUROCRYPT
2003
FSE
2003
FSE
2003
JOFC
2002
CRYPTO
2002
EUROCRYPT
2002
FSE
2001
PKC
2001
EPRINT
Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups
Antoine Joux Kim Nguyen
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
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.
2000
ASIACRYPT
2000
CRYPTO
2000
EUROCRYPT
2000
FSE
1998
CRYPTO
1998
JOFC
1994
EUROCRYPT
1991
ASIACRYPT
1991
CRYPTO

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