Paper 2017/720

Computing Low-Weight Discrete Logarithms

Bailey Kacsmar, Sarah Plosker, and Ryan Henry

Abstract

We propose some new baby-step giant-step algorithms for computing "low-weight" discrete logarithms; that is, for computing discrete logarithms in which the radix-b representation of the exponent is known to have only a small number of nonzero digits. Prior to this work, such algorithms had been proposed for the case where the exponent is known to have low Hamming weight (i.e., the radix-2 case). Our new algorithms (i) improve the best-known deterministic complexity for the radix-2 case, and then (ii) generalize from radix-2 to arbitrary radixes b>1. We also discuss how our new algorithms can be used to attack several recent Verifier-based Password Authenticated Key Exchange (VPAKE) protocols from the cryptographic literature with the conclusion that the new algorithms render those constructions completely insecure in practice.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. The 24th Annual Conference on Selected Areas in Cryptography (SAC 2017)
Keywords
discrete logarithm problemnumber theorybaby-step giant-stepmeet-in-the-middlecryptanalysis
Contact author(s)
henry @ indiana edu
History
2017-07-27: received
Short URL
https://ia.cr/2017/720
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/720,
      author = {Bailey Kacsmar and Sarah Plosker and Ryan Henry},
      title = {Computing Low-Weight Discrete Logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/720},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/720}},
      url = {https://eprint.iacr.org/2017/720}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.