Paper 2020/416
The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures
Mihir Bellare and Wei Dai
Abstract
We introduce the Multi-Base Discrete Logarithm (MBDL) problem. We use this to give reductions, for Schnorr and Okamoto identification and signatures, that are non-rewinding and, by avoiding the notorious square-root loss, tighter than the classical ones from the Discrete Logarithm (DL) problem. This fills a well-known theoretical and practical gap regarding the security of these schemes. We show that not only is the MBDL problem hard in the generic group model, but with a bound that matches that for DL, so that our new reductions justify the security of these primitives for group sizes in actual use.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Major revision. INDOCRYPT 2020: 20th International Conference on Cryptology in India
- Keywords
- Schnorr IdentificationSchnorr Signaturesrandom-oracle modelreduction tightnessDiscrete logarithm problemsecurity proofs
- Contact author(s)
-
mihir @ eng ucsd edu
weidai @ eng ucsd edu - History
- 2020-10-24: last of 2 revisions
- 2020-04-13: received
- See all versions
- Short URL
- https://ia.cr/2020/416
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/416,
author = {Mihir Bellare and Wei Dai},
title = {The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/416},
year = {2020},
url = {https://eprint.iacr.org/2020/416}
}
