Paper 2021/866

The One-More Discrete Logarithm Assumption in the Generic Group Model

Balthazar Bauer, Georg Fuchsbauer, and Antoine Plouviez


The one more-discrete logarithm assumption (OMDL) underlies the security analysis of identification protocols, blind signature and multi-signature schemes, such as blind Schnorr signatures and the recent MuSig2 multi-signatures. As these schemes produce standard Schnorr signatures, they are compatible with existing systems, e.g. in the context of blockchains. OMDL is moreover assumed for many results on the impossibility of certain security reductions. Despite its wide use, surprisingly, OMDL is lacking any rigorous analysis; there is not even a proof that it holds in the generic group model (GGM). (We show that a claimed proof is flawed.) In this work we give a formal proof of OMDL in the GGM. We also prove a related assumption, the one-more computational Diffie-Hellman assumption, in the GGM. Our proofs deviate from prior proofs in the GGM and replace the use of the Schwartz-Zippel Lemma by a new argument.

Available format(s)
Publication info
Preprint. MINOR revision.
One-more discrete logarithmgeneric group modelblind signaturesmulti-signatures
Contact author(s)
balthazar bauer @ ens fr
georg fuchsbauer @ tuwien ac at
antoine plouviez @ ens fr
2021-06-24: received
Short URL
Creative Commons Attribution


      author = {Balthazar Bauer and Georg Fuchsbauer and Antoine Plouviez},
      title = {The One-More Discrete Logarithm Assumption in the Generic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2021/866},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.