International Association for Cryptologic Research

International Association
for Cryptologic Research


Jaime Gutierrez


Improving Key-Recovery in Linear Attacks: Application to 28-round PRESENT 📺
Antonio Flórez Gutiérrez María Naya-Plasencia
Linear cryptanalysis is one of the most important tools in use for the security evaluation of symmetric primitives. Many improvements and refinements have been published since its introduction, and many applications on different ciphers have been found. Among these upgrades, Collard et al. proposed in 2007 an acceleration of the key-recovery part of Algorithm 2 for last-round attacks based on the FFT. In this paper we present a generalized, matrix-based version of the previous algorithm which easily allows to take into consideration an arbitrary number of key-recovery rounds. We also provide efficient variants that exploit the key-schedule relations and that can be combined with multiple linear attacks. Using our algorithms we provide some new cryptanalysis on PRESENT, including, to the best of our knowledge, the first attack on 28 rounds.
An Algorithm for Finding Small Roots of Multivariate Polynomials over the Integers
Domingo Gomez Jaime Gutierrez Alvar Ibeas
In this paper we present a new algorithm for finding small roots of a system of multivariate polynomials over the integers based on lattice reduction techniques. Our simpler heuristic method is inspired in algorithms for predicting pseudorandom numbers, and it can be considered as another variant of Coppersmith's method for finding small solutions of integer bivariate polynomials. We also apply the method to the well known problem of factoring an integer when we know the high-order bits of one of the factors.
Inferring sequences produced by a linear congruential generator on elliptic curves missing high--order bits
Jaime Gutierrez Alvar Ibeas
Let $p$ be a prime and let $E(\F_p)$ be an elliptic curve defined over the finite field $\F_p$ of $p$ elements. For a given point $G \in E(\F_p)$ the linear congruential genarator on elliptic curves (EC-LCG) is a sequence $(U_n)$ of pseudorandom numbers defined by the relation $$ U_n=U_{n-1}\oplus G=nG\oplus U_0,\quad n=1,2,\ldots,$$ where $\oplus$ denote the group operation in $E(\F_p)$ and $U_0 \in E(\F_p)$ is the initial value or seed. We show that if $G$ and sufficiently many of the most significants bits of two consecutive values $U_n, U_{n+1}$ of the EC-LCG are given, one can recover the seed $U_0$ (even in the case where the elliptic curve is private) provided that the former value $U_n$ does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where $G$ is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.