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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/416}},
      url = {https://eprint.iacr.org/2020/416}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.