International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Low Weight Discrete Logarithms and Subset Sum in $2^{0.65n}$ with Polynomial Memory

Andre Esser , Ruhr University Bochum
Alexander May , Ruhr University Bochum
DOI: 10.1007/978-3-030-45727-3_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
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}$.
Video from EUROCRYPT 2020
  title={Low Weight Discrete Logarithms and Subset Sum in $2^{0.65n}$ with Polynomial Memory},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={Low weight dlog;subset sum;representations;Nested Rho},
  author={Andre Esser and Alexander May},