International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Balthazar Bauer , IRIF
Georg Fuchsbauer , TU Wien
Antoine Plouviez , Inria/ENS
DOI: 10.1007/978-3-030-92068-5_20
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: 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 GGM proofs and replace the use of the Schwartz-Zippel Lemma by a new argument.
Video from ASIACRYPT 2021
  title={The One-More Discrete Logarithm Assumption in the Generic Group Model},
  author={Balthazar Bauer and Georg Fuchsbauer and Antoine Plouviez},