## 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
📺
Abstract

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
📺
Abstract

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
Abstract

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

2012

EUROCRYPT

2010

PKC

2009

ASIACRYPT

2007

CRYPTO

2007

EPRINT

On Factoring Arbitrary Integers with Known Bits
Abstract

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.

2006

ASIACRYPT

2004

EPRINT

Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Abstract

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.

#### 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

#### Coauthors

- Anja Becker (1)
- Daniel Bleichenbacher (1)
- Johannes Blömer (3)
- Leif Both (1)
- Jean-Sébastien Coron (2)
- Matthias Ernst (1)
- Andre Esser (3)
- Wilko Henecka (1)
- Gottfried Herold (1)
- Mathias Herrmann (4)
- Felix Heuer (1)
- Ellen Jochemsz (3)
- Antoine Joux (1)
- Saqib A. Kakvi (1)
- Eike Kiltz (1)
- Robert Kübler (2)
- Gregor Leander (1)
- Alexander Meurer (3)
- Ilya Ozerov (1)
- Maike Ritzenhofen (2)
- Christian Sohler (1)
- Enrico Thomae (1)
- Benne de Weger (1)