International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alexander May

Affiliation: CNRS and ENS de Lyon, FR

Publications

Year
Venue
Title
2020
EUROCRYPT
Low Weight Discrete Logarithms and Subset Sum in $2^{0.65n}$ with Polynomial Memory 📺
Andre Esser Alexander May
We propose two heuristic polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group $G$. The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight discrete logarithm algorithms, our second algorithm's time complexity interpolates to Pollard's $|G|^{\frac 1 2}$ bound for general discrete logarithm instances. We also introduce a new heuristic subset sum algorithm with polynomial memory that improves on BCJ's $2^{0.72n}$ time bound for random subset sum instances $a_1, \ldots, a_n, t \in \Z_{2^n}$. Technically, we introduce a novel nested collision finding for subset sum -- inspired by the NestedRho algorithm from Crypto '16 -- that recursively produces collisions. We first show how to instantiate our algorithm with run time $2^{0.649n}$. Using further tricks, we are then able to improve its complexity down to $2^{0.645n}$.
2018
CRYPTO
Dissection-BKW 📺
The slightly subexponential algorithm of Blum, Kalai and Wasserman (BKW) provides a basis for assessing LPN/LWE security. However, its huge memory consumption strongly limits its practical applicability, thereby preventing precise security estimates for cryptographic LPN/LWE instantiations.We provide the first time-memory trade-offs for the BKW algorithm. For instance, we show how to solve LPN in dimension k in time $$2^{\frac{4}{3} \frac{k}{\log k} }$$ and memory $$2^{\frac{2}{3} \frac{k}{\log k} }$$. Using the Dissection technique due to Dinur et al. (Crypto ’12) and a novel, slight generalization thereof, we obtain fine-grained trade-offs for any available (subexponential) memory while the running time remains subexponential.Reducing the memory consumption of BKW below its running time also allows us to propose a first quantum version QBKW for the BKW algorithm.
2017
TOSC
The Approximate k-List Problem
Leif Both Alexander May
We study a generalization of the k-list problem, also known as the Generalized Birthday problem. In the k-list problem, one starts with k lists of binary vectors and has to find a set of vectors – one from each list – that sum to the all-zero target vector. In our generalized Approximate k-list problem, one has to find a set of vectors that sum to a vector of small Hamming weight ω. Thus, we relax the condition on the target vector and allow for some error positions. This in turn helps us to significantly reduce the size of the starting lists, which determines the memory consumption, and the running time as a function of ω. For ω = 0, our algorithm achieves the original k-list run-time/memory consumption, whereas for ω = n/2 it has polynomial complexity. As in the k-list case, our Approximate k-list algorithm is defined for all k = 2m,m > 1. Surprisingly, we also find an Approximate 3-list algorithm that improves in the runtime exponent compared to its 2-list counterpart for all 0 < ω < n/2. To the best of our knowledge this is the first such improvement of some variant of the notoriously hard 3-list problem. As an application of our algorithm we compute small weight multiples of a given polynomial with more flexible degree than with Wagner’s algorithm from Crypto 2002 and with smaller time/memory consumption than with Minder and Sinclair’s algorithm from SODA 2009.
2017
PKC
2017
CRYPTO
2017
ASIACRYPT
2015
EUROCRYPT
2012
EUROCRYPT
2012
ASIACRYPT
2011
ASIACRYPT
2010
PKC
2010
CRYPTO
2009
ASIACRYPT
2009
PKC
2008
PKC
2008
ASIACRYPT
2007
CRYPTO
2007
EPRINT
On Factoring Arbitrary Integers with Known Bits
Mathias Herrmann Alexander May
We study the {\em factoring with known bits problem}, where we are given a composite integer $N=p_1p_2\dots p_r$ and oracle access to the bits of the prime factors $p_i$, $i=1, \dots, r$. Our goal is to find the full factorization of $N$ in polynomial time with a minimal number of calls to the oracle. We present a rigorous algorithm that efficiently factors $N$ given $(1-\frac{1}{r}H_r)\log N$ bits, where $H_r$ denotes the $r^{th}$ harmonic number.
2007
JOFC
2006
ASIACRYPT
2006
PKC
2005
EUROCRYPT
2005
EUROCRYPT
2004
CRYPTO
2004
PKC
2004
PKC
2004
EPRINT
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Jean-Sébastien Coron Alexander May
We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key-pair (e,d) yield the factorization of N=pq in polynomial time? It is well-known that there is a probabilistic polynomial time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial time algorithm that factors N provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.
2003
CRYPTO
2002
CRYPTO

Program Committees

Eurocrypt 2020
Asiacrypt 2017
Crypto 2016
Asiacrypt 2016
PKC 2016
Asiacrypt 2015
Crypto 2014
Eurocrypt 2014
PKC 2013
Crypto 2012
PKC 2011
Eurocrypt 2011
Eurocrypt 2010
PKC 2008
Asiacrypt 2007
Eurocrypt 2007
PKC 2006
Eurocrypt 2006