Computing Low-Weight Discrete Logarithms

Bailey Kacsmar; Sarah Plosker; Ryan Henry

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 problem number theory baby-step giant-step meet-in-the-middle cryptanalysis
Contact author(s): henry @ indiana edu
History: 2017-07-27: received
Short URL: https://ia.cr/2017/720
License: 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},
      url = {https://eprint.iacr.org/2017/720}
}