The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures

Mihir Bellare and Wei Dai | INDOCRYPT 2020

發表於 2026-03-04 | 更新於 2026-04-14 | square-root-barrier paper MBDL

Abstract

本文提出 Multi-Base Discrete Logarithm (MBDL) 問題，並以此為基礎，為 Schnorr 與 Okamoto 的 identification 與 signatures 建立 non-rewinding 的 reductions，從而避免傳統 reductions 常見的 square-root loss，使歸約更為 tighter，並補足相關 schemes 在理論與實務安全性分析上的缺口。

此外，本文證明 MBDL 在 generic group model 中具有與 Discrete Logarithm (DL) 相匹配的困難度 bound，因此可在實際使用的 group sizes 下，為上述 primitives 的 security 提供更堅實的理論依據。

Introduction

See 1 Introduction.

Preliminaries

See 2 Preliminaries.

The Multi-Base Discrete Logarithm Problem

See 3 The Multi-Base Discrete Logarithm Problem.

Schnorr Identification and Signatures from MBDL

See 4 Schnorr Identification and Signatures from MBDL.

Background notes:

• 4.1 Schnorr Identification from MBDL
• 4.2 Schnorr Signature from MBDL
• Proof of Theorem 4.1

MBDL hardness in the Generic Group Model

See 5 MBDL hardness in the Generic Group Model.

A Okamoto Identification and Signature from MBDL

See A Okamoto Identification and Signature from MBDL.

B Ratio-based tightness

See B Ratio-based tightness.

References

• BD20 M. Bellare and W. Dai. The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures. In Progress in Cryptology-INDOCRYPT '20, pages 529-552, 2020.