Paper 2017/1113

The Discrete-Logarithm Problem with Preprocessing

Henry Corrigan-Gibbs and Dmitry Kogan

Abstract

This paper studies discrete-log algorithms that use preprocessing. In our model, an adversary may use a very large amount of precomputation to produce an "advice" string about a specific group (e.g., NIST P-256). In a subsequent online phase, the adversary's task is to use the preprocessed advice to quickly compute discrete logarithms in the group. Motivated by surprising recent preprocessing attacks on the discrete-log problem, we study the power and limits of such algorithms. In particular, we focus on generic algorithms -- these are algorithms that operate in every cyclic group. We show that any generic discrete-log algorithm with preprocessing that uses an $S$-bit advice string, runs in online time $T$, and succeeds with probability $\epsilon$, in a group of prime order $N$, must satisfy $ST^2 = \tilde{\Omega}(\epsilon N)$. Our lower bound, which is tight up to logarithmic factors, uses a synthesis of incompressibility techniques and classic methods for generic-group lower bounds. We apply our techniques to prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems. Finally, we demonstrate two new generic preprocessing attacks: one for the multiple-discrete-log problem and one for certain decisional-type problems in groups. This latter result demonstrates that, for generic algorithms with preprocessing, distinguishing tuples of the form $(g, g^x, g^{(x^2)})$ from random is much easier than the discrete-log problem.

Note: This version adds a clarifying remark after Proposition 1.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Keywords
discrete logarithm problemgeneric-group model
Contact author(s)
henrycg @ cs stanford edu
dkogan @ cs stanford edu
History
2021-08-03: last of 8 revisions
2017-11-20: received
See all versions
Short URL
https://ia.cr/2017/1113
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1113,
      author = {Henry Corrigan-Gibbs and Dmitry Kogan},
      title = {The Discrete-Logarithm Problem with Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1113},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1113}},
      url = {https://eprint.iacr.org/2017/1113}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.