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-03-05 square-root-barrier paper

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 提供更堅實的理論依據。

Schnorr Schemes

Schnorr schemes 定義在一個 prime-order group $G$ 上，其 order 為 $p$，並令 $g \in G$ 為其 generator Sch91。

  • $ \mathrm{ID} = \mathrm{SchID}[G,g] $ 表示 Schnorr identification scheme
  • $ \mathrm{DS} = \mathrm{SchSig}[G,g] $ 表示 Schnorr signature scheme

Schnorr Identification 的安全目標

Schnorr identification scheme 的安全目標是 IMP-PA（impersonation under passive attack）FFS88。

這表示 adversary 只能 passively 觀察 honest prover 與 verifier 之間的 transcripts，不能主動操控或額外與 prover 互動；接著 adversary 的目標是要成功 impersonate 合法的 prover。

因此，IMP-PA 衡量的是：攻擊者在只看過互動紀錄的情況下，是否仍能冒充 prover。

Schnorr Signature 的來源

Schnorr signature scheme 是由 Schnorr identification scheme 經過 Fiat–Shamir transform 得到的 FS87。

其核心想法是：

  • 原本的 identification protocol 是 interactive
  • verifier 原本會送出一個 random challenge
  • 在 Fiat–Shamir transform 中，這個 challenge 改由 hash function 產生
  • 因此可將原本的 interactive protocol 轉成 non-interactive signature scheme

Schnorr Signature 的安全目標

Schnorr signature scheme 的安全目標是 UF-CMA（unforgeability under chosen-message attack）GMR88。

而這個安全性通常是在 ROM（Random Oracle Model）下討論 BR93。

UF-CMA 的意思是：

  • adversary 可以自行選擇 message
  • 並向 signing oracle 查詢這些 message 的合法 signature
  • 但最後仍不應能產生新的有效 forgery

也就是說，即使 adversary 有 chosen-message attack 的能力，也不能偽造新的 Schnorr signature。

References

  • Sch91 C.-P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991.
  • FFS88 U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
  • FS87 A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages 186–194, 1987.
  • GMR88 S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen message attacks. SIAM Journal on Computing, 17(2):281–308, 1988.
  • BR93 M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM CCS 93, pages 62–73, 1993.
↑