[BD20] 1 Introduction

Mihir Bellare and Wei Dai INDOCRYPT 2020
發表於 2026-04-09 更新於 2026-04-14 square-root-barrier paper MBDL

It is chapter 1 of the paperBD20. Other chapters include:

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

Security Goal of 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。

Derivation of Schnorr Signatures

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

Security Goal of Schnorr Signatures

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。

The Situation with $\mathrm{ID}$

Tiers and Knobs

MBDL

See 3 The Multi-Base Discrete Logarithm Problem.

Core Results

What Has Been Gained

Reduction Approaches

MBDL As A Hub

BN

Bellare-Neven multi-signatures BN06 是經典的 Schnorr-type multi-signature。多個簽署者共同對同一訊息簽署，最終輸出一個短簽章，而不是把每位簽署者的個別簽章全部串接起來。

這類方案的重要要求包括能抵抗 rogue-key attack、支援 plain public-key model，並在多簽署者情境下仍保有良好的效率與短簽章特性。從結構上看，BN multi-signature 可以理解為將多個 Schnorr-style 簽署過程結合起來，因此它是最自然的 Schnorr-family 擴張之一。

MBDL 論文將 Bellare–Neven multi-signatures 列為 follow-up 方向之一，表示作者認為這類 primitive 有可能沿著 Schnorr / Okamoto 的路徑，進一步獲得以 MBDL 為基礎的緊密安全歸約。不過，就目前公開可確認的後續成果而言，尚未看到一篇 reduction 論文明確完成

\[\text{BN multi-signatures} \;\longleftarrow\; \text{MBDL}\]

Chain Reductions

目前可確認的公開後續工作是 Chain Reductions for Multi-Signatures and the HBMS Scheme。這篇確實處理了 BN scheme，但它採用的技術路線不是 MBDL，而是透過 chain reductions 將 proof 拆成數個中介問題上的歸約步驟。其核心想法不是直接從 DL 一步歸約到目標 primitive，而是插入一些中間問題，形成一條 reduction chain。一般形式是

\[DL = P_0 \to P_1 \to \cdots \to P_m = MS.\]

在這篇論文中，作者採用的中間問題包括 IDL 與 XIDL，對應的路徑例如

\[DL \to IDL \to BN\]

以及

\[DL \to IDL \to XIDL \to MuSig\]

和

\[DL \to IDL \to XIDL \to HBMS.\]

這裡的重點不是單純多設幾個問題，而是透過中介問題把原本直接又鬆的歸約拆解成多步，使每一步都更容易分析，並且可以同時得到 tight AGM reduction 與到中介假設的 standard-model reduction。

就這個意義上，chain reductions 提供的是一條替代 MBDL 的技術路線：當直接從 DL 對 multi-signatures 做緊密 standard-model 歸約看起來很困難時，可以透過 IDL / XIDL 這些中間問題建立更有結構的 proof。

MBDL 的做法是更換一個更強、但仍具數論意義的中介假設，用它直接捕捉 Schnorr 型結構中 classical DL proof 無法緊密表達的那部分 hardness，從而達成 non-rewinding 且較緊的 reduction；chain reductions 的做法則是承認直接從 DL 到目標 primitive 很難，因此改以插入 IDL / XIDL 等中間問題的方式，在 AGM 或標準模型下分段建立更可控制的 reduction。

兩者都可以被視為調整 proof framework 的方法，但前者偏向「改 assumption，保留 tight standard-model aspiration」，後者則偏向「改 proof architecture，接受 intermediate problems 與 AGM」。

因此，對 BN multi-signatures 而言，可以說它確實是 MBDL 論文明確點名的後續方向之一，但目前公開文獻中尚未看到真正完成的 BN to MBDL reduction；相反地，公開後續工作選擇了 IDL / XIDL + AGM 這條路，這也使得「MBDL 能否作為 multi-signatures 的緊密歸約起點」仍然可以被視為一個 open direction。

AOS

Abe, Ohkubo, Suzuki 1-out-of-(n) (ring/group) signatures AOS02 屬於匿名簽章類 primitive。其核心語意是：給定一組 public keys，驗證者只能確定這組人之中有一位簽了訊息，但無法知道究竟是哪一位。

因此，和一般 Schnorr signature 相比，這類方案除了 unforgeability 之外，還帶有匿名性與 OR-composition 的結構。

從 Schnorr-family 的觀點看，AOS 類方案的一個重要特徵是只存在一個真實 witness，其餘部分透過模擬或 OR-proof 結構完成，因此整體上仍然保有相當強的 Schnorr-style flavor。

MBDL 論文將 AOS ring/group signatures 列入 follow-up 方向，表示作者認為這類 primitive 也可能有機會接受 MBDL-style 的緊密歸約。直覺上，AOS 類方案比 multi-signature 或 threshold signature 更接近單一 signer / 單一 witness 的場景，因此看起來也較接近 BD20 成功處理的 Schnorr / Okamoto 結構，這也是它常被視為一個潛在有吸引力的研究起點的原因。

不過，這種判斷目前仍應保持保留。就目前公開可確認的文獻而言，尚無證據顯示 AOS 比 BN multi-signatures 或 Schnorr-based threshold signatures 更容易建立到 MBDL 的歸約；此外，AOS 雖然只有一個真實 signer，但其 OR-composition、ring closure 與匿名性要求，也可能引入不同於單一 Schnorr signature 的新技術障礙。因此，較穩妥的說法是：AOS 是一個合理且值得優先考慮的 MBDL 延伸目標之一，但目前沒有公開證據能證明它一定比其他方向更容易成功。

Threshold Signatures

Schnorr-based threshold signatures SS01 的目標是：在 (n) 個參與者中，只需要其中 (t) 個合作，就能產生一個整體有效的簽章。

這類 primitive 在實務上非常重要，因為它對應分散式金鑰管理、多方授權、wallet custody 以及 MPC-based signing 等應用場景。若其底層簽章是 Schnorr 型，則通常可視為 Schnorr-family primitive 的另一種延伸。

MBDL 論文同樣將 Schnorr-based threshold signatures 列為 follow-up 方向，表示作者預期 MBDL 的技術也許有機會延伸到 threshold setting。

不過，threshold signatures 比單一 Schnorr signature 顯著複雜，因為它通常涉及多個局部 secret shares、多方 nonce 協調、聚合與子集合選擇，並且可能還帶有 robustness、identifiable abort 或 preprocessing 等額外要求。

因此，即使其底層精神仍屬於 Schnorr-family，實際 proof structure 往往比單一 signer primitive 困難得多。就目前公開可確認的資料而言，尚未看到一篇明確完成

\[\text{threshold signature} \;\longleftarrow\; \text{MBDL}\]

這種歸約的後續 paper。換言之，這條線至少在目前可見的公開文獻中，仍然是一個尚未完成的研究方向。

Remark. 從研究直覺來看，MBDL 論文所提到的三條後續方向可以粗略分成兩類：AOS ring/group signatures 較接近單一 witness、單一 signer 的結構，而 BN multi-signatures 與 Schnorr-based threshold signatures 則帶有較重的多方互動成分。
這個差異之所以重要，在於 BD20 中 MBDL 成功處理的 Schnorr / Okamoto 證明，核心上都偏向單一 witness 的範式；相較之下，多方互動 primitive 往往包含更複雜的代數依賴與協作狀態，因此未必能直接沿用 BD20 的 planting 與 non-rewinding 技巧。
基於這點，可以形成較保守的研究判斷：AOS 由於仍保有單一真實 witness 的 Schnorr-style 結構，因此作為 MBDL 延伸目標具有吸引力；BN multisignatures 雖然已有公開後續工作處理，但該工作走的是 IDL / XIDL + AGM 路線，而不是 MBDL；threshold signatures 雖然應用價值很高，但結構通常也最複雜，因此若直接從 MBDL 出發，技術風險可能更高。
不過，這並不代表 AOS 已知一定最容易成功；較準確的說法是，AOS、BN multisignatures 與 Schnorr-based threshold signatures 都是合理的 MBDL 延伸目標，但目前沒有公開文獻能證明哪一個一定最容易完成。
若以接近 BD20 的單一 signer 技術模式為優先考量，AOS 可能是值得優先嘗試的方向；若以和既有公開後續成果接軌為優先考量，則 BN multisignatures 會是更自然的起點。

Discussion

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.
  • 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.
  • BN06 M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In A. Juels, R. N. Wright, and S. De Capitani di Vimercati, editors, ACM CCS 2006, pages 390–399. ACM Press, Oct./Nov. 2006.
  • AOS02 M. Abe, M. Ohkubo, and K. Suzuki. 1-out-of-n signatures from a variety of keys. In Y. Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 415–432. Springer, Heidelberg, Dec. 2002.
  • SS01 D. R. Stinson and R. Strobl. Provably secure distributed Schnorr signatures and a (t, n) threshold scheme for implicit certificates. In V. Varadharajan and Y. Mu, editors, ACISP 2001, volume 2119 of LNCS, pages 417–434. Springer, Heidelberg, July 2001.
↑