Cryptology ePrint Archive: Report 2021/866

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

Balthazar Bauer and Georg Fuchsbauer and Antoine Plouviez

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 proofs in the GGM and replace the use of the Schwartz-Zippel Lemma by a new argument.

Category / Keywords: foundations / One-more discrete logarithm, generic group model, blind signatures, multi-signatures

Date: received 24 Jun 2021, last revised 24 Jun 2021

Contact author: balthazar bauer at ens fr, georg fuchsbauer at tuwien ac at, antoine plouviez at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20210624:150822 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]