Paper 2019/931

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

Andre Esser and Alexander May

Abstract

We propose two 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 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 \mathbb{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}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2020
Keywords
Low weight dlogsubset sumrepresentationsNested Rho
Contact author(s)
andre esser @ rub de
History
2020-02-06: revised
2019-08-18: received
See all versions
Short URL
https://ia.cr/2019/931
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/931,
      author = {Andre Esser and Alexander May},
      title = {Low Weight Discrete Logarithms and Subset Sum in $2^{0.65n}$ with Polynomial Memory},
      howpublished = {Cryptology ePrint Archive, Paper 2019/931},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/931}},
      url = {https://eprint.iacr.org/2019/931}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.