Cryptology ePrint Archive: Report 2020/416

The Multi-Base Discrete Logarithm Problem: Non-Rewinding Proofs and Improved Reduction Tightness for Identification and Signatures

Mihir Bellare and Wei Dai

Abstract: We introduce the Multi-Base Discrete Logarithm (MBDL) problem. We use this to give, for various schemes, reductions that are non-rewinding and tighter (in some cases, optimally so) than the classical ones from the Discrete Logarithm (DL) problem. The schemes include (1) Schnorr identification and signatures (2) Okamoto identification and signatures (3) Bellare-Neven multi-signatures (4) Abe, Ohkubo, Suzuki 1-out-of-n (ring/group) signatures and (5) Schnorr-based threshold signatures. 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 allow implementations, for the same level of proven security, to use smaller groups, which increases efficiency.

Category / Keywords: public-key cryptography / Schnorr Identification, Schnorr Signatures, Multi-signatures, Ring signatures, 1-out-of-n signatures, random-oracle model, reduction tightness, Discrete logarithm problem, security proofs

Date: received 13 Apr 2020, last revised 21 May 2020

Contact author: mihir at eng ucsd edu,weidai@eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20200521:175824 (All versions of this report)

Short URL: ia.cr/2020/416


[ Cryptology ePrint archive ]