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
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
-
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}, url = {https://eprint.iacr.org/2017/1113} }