Paper 2017/720 Original: eprint.iacr.org/2017/720 ↗
Computing Low-Weight Discrete Logarithms
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
- Preprint.
- History
- 2017-07-27: last updated
- 2017-07-27: published
- Short URL
- https://ia.cr/2017/720
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}