[BD20] 4.2 Schnorr Signature from MBDL
This note is subchapter 4.2 of chapter 4 Schnorr Identification and Signatures from MBDL in the paperBD20. The companion subchapter is 4.1 Schnorr Identification from MBDL. Other chapters include:
- 1 Introduction
- 2 Preliminaries
- 3 The Multi-Base Discrete Logarithm Problem
- 4.1 Schnorr Identification from MBDL
- 5 MBDL hardness in the Generic Group Model
- A Okamoto Identification and Signature from MBDL
- B Ratio-based tightness
Signature Schemes and the Transfer from IMP-PA to UF
Signature schemes
先回顧 signature scheme 的抽象形式。
一個 signature scheme 可以寫成
$DS = (\mathrm{Kg}, \mathrm{Sign}, \mathrm{Vf}, \mathrm{HF})$，
對應 key generation、signing、verification，以及 hash-function space。
在 UF game 中，先取 \(h \gets DS.\mathrm{HF},\) 然後 adversary 可以查詢 signing oracle，最後若能產生一組新的有效 message-signature pair，且該 message 並未送進過 signing oracle，就算 forgery 成功。
Schnorr signatures
Schnorr signature scheme 記為 \(DS = \mathrm{SchSig}[G, g].\)
它可以視為由 Schnorr identification scheme 經 Fiat–Shamir transform 得到。
對應的 hash function space 是把
$G \times {0,1}^\ast$
映到
$\mathbb{Z}_p$
的函數族。
From UF to IMP-PA
本文的策略不是直接從 1-MBDL 去證明簽章的 UF-security，而是先把簽章安全性轉換成 identification scheme 的 IMP-PA 安全性，再接上前一節給出的 tight reduction。
換句話說，proof 結構分成兩步：
- 先把 Schnorr signatures 的 UF 攻擊轉成對 Schnorr identification 的 IMP-PA 攻擊。
- 再把這個 IMP-PA 攻擊用 1-MBDL tight reduction 吸收掉。
這樣可以避開傳統 Forking Lemma 路線常見的鬆弛損失，並得到 chapter 4 後面更乾淨的 quantitative bound。
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.