International Association for Cryptologic Research

International Association
for Cryptologic Research


Reynald Lercier


Grøstl Distinguishing Attack: A New Rebound Attack of an AES-like Permutation
We consider highly structured truncated differential paths to mount a new rebound attack on Grøstl-512, a hash functions based on two AES-like permutations, P1024 and Q1024, with non-square input and output registers. We explain how such differential paths can be computed using a Mixed-Integer Linear Programming approach. Together with a SuperSBox description, this allows us to build a rebound attack with a 6-round inbound phase whereas classical rebound attacks have 4-round inbound phases. This yields the first distinguishing attack on a 11-round version of P1024 and Q1024 with about 272 computations and a memory complexity of about 256 bytes, to be compared with the 296 computations required by the corresponding generic attack. Previous best results on this permutation reached 10 rounds with a computational complexity of about 2392 operations, to be compared with the 2448 computations required by the corresponding generic attack.
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$.
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.
FRMAC, a Fast Randomized Message Authentication Code
Éliane Jaulmes Reynald Lercier
We revisit the randomized approach followed in the design of the RMAC message authentication code in order to construct a MAC with similar properties, but based on Wegman-Carter's $\varepsilon$-universal hash families instead of a classical CBC chain. This yields a new message authentication code called FRMAC whose security bounds are, as in RMAC, beyond the birthday paradox limit. With efficient hash functions in software, the performance of FRMAC for large messages is similar to those of the fastest previously known schemes. FRMAC can also be more efficient for small messages. Furthermore, due to relaxed requirements about the nonces in the security proof, the implementation of FRMAC in real applications tends to be easier.

Program Committees

PKC 2010
Eurocrypt 2009