Paper 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.