Paper 2012/458

Computing small discrete logarithms faster

Daniel J. Bernstein and Tanja Lange

Abstract

Computations of small discrete logarithms are feasible even in "secure" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh--Goh--Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.21*l^{2/3} multiplications, and computing a discrete logarithm in a group of order l takes only 1.77*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.24*l^{2/3} multiplications.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
discrete logarithmsrandom walksprecomputation
Contact author(s)
tanja @ hyperelliptic org
History
2012-09-20: revised
2012-08-13: received
See all versions
Short URL
https://ia.cr/2012/458
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/458,
      author = {Daniel J.  Bernstein and Tanja Lange},
      title = {Computing small discrete logarithms faster},
      howpublished = {Cryptology ePrint Archive, Paper 2012/458},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/458}},
      url = {https://eprint.iacr.org/2012/458}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.