Cryptology ePrint Archive: Report 2017/720

Computing Low-Weight Discrete Logarithms

Bailey Kacsmar and 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.

Category / Keywords: foundations / discrete logarithm problem, number theory, baby-step giant-step, meet-in-the-middle, cryptanalysis, verifier-based password authenticated key exchange (VPAKE)

Original Publication (in the same form): The 24th Annual Conference on Selected Areas in Cryptography (SAC 2017)

Date: received 25 Jul 2017

Contact author: henry at indiana edu

Available format(s): PDF | BibTeX Citation

Version: 20170727:182104 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]