Tighter Security for Schnorr Identification and Signature: A High-Moment Forking Lemma for Sigma-Protocols
Abstract
Schnorr identification and signature schemes 一直是過去三十年中最具影響力的 cryptographic protocols 之一。不幸的是，雖然目前對這兩個 schemes 最知名的 attacks 都是透過 discrete logarithm computation，但想把它們的 security 建立在 discrete logarithm problem 的 hardness 上，既有作法會遇到所謂的 square-root barrier。
Schnorr identification scheme 是一個互動式的三階段（commit → challenge → response）
Σ-protocol：
- Prover 先送出承諾 $a=g^r$
- Verifier 給隨機挑戰 $e$
- Prover 回應 $z=r+ex$
- Verifier 檢查 $g^z \stackrel{?}{=} a\cdot y^e$（其中公開金鑰 $y=g^x$）
Schnorr signature scheme 則可視為把上述互動協定用 Fiat–Shamir transform 去互動化：
把挑戰改成 $e = H(m \,\|\, a)$，並在 random oracle model (ROM) 中把 $H$ 視為 random oracle。
簽章為回應值（例如 $z$，搭配 $e$ 或 $a$），驗證時重建/檢查對應的 $a$ 與 hash 是否一致。
對 Schnorr identification 與 Schnorr signature 目前最典型、也最強的攻擊路線，本質上都等價於先解 discrete logarithm（從 $y=g^x$ 求出 $x$）。一旦拿到秘密金鑰 $x$：
- 對 Schnorr identification：attacker 就能直接扮演 Prover，對任何 challenge $e$ 都能產生正確 response $z=r+ex$，因此完成 impersonation。
- 對 Schnorr signature：attacker 就能對任意訊息 $m$ 自行產生合法簽章（因為簽章演算法本來就只需要 $x$），因此達成 forgery。
因此「最知名的 attack」不是指某個對協定結構的特殊破綻，而是指：破解它們最直接的方法就是把問題降回去解 discrete log； 在參數設定常用的群中，這通常對應到已知的 square-root 類型離散對數演算法（所以文中用 $t^2/p$ 這種量級來描述 $t$ 時間內的成功率）。
更具體地說，在任何 order 為 $p$ 的 group 中，如果我們相信 Shoup 的 generic hardness result 對 discrete logarithm problem 成立（並因此用它來設定 concrete security parameters），那麼已知最佳的 $t$-time attacks 對 Schnorr identification 與 signature schemes 的 success probability 為
\[\frac{t^2}{p},\]然而現有的 security proofs 只能排除 success probabilities 分別達到
\[\left(\frac{t^2}{p}\right)^{1/2} \quad\text{以及}\quad \left(\frac{q_H \cdot t^2}{p}\right)^{1/2}\]的 attacks；其中 $q_H$ 表示 attacker 發出的 random oracle queries 數量。
在 Shoup 的 generic group model（且群階為 $p$）的語境下：
$p$ 是 group 的 order（元素總數，通常是大質數），
$t$ 是 attacker 的 running time / 資源上限（常可理解為能做的 generic group operations 或 oracle queries 的數量上界）。
因此「$t$-time 內成功率約 $t^2/p$」是在表達：在 generic 設定裡，攻擊者做越多群運算成功率越高，但會被群大小 $p$ 壓制。
原文提到的兩個 success probability 上界，確實是分別對應 Schnorr 的 identification 與 signature：
-
Schnorr identification（互動式，不用 random oracle）：
現有 proofs 只能排除 success probability 到 $$ \left(\frac{t^2}{p}\right)^{1/2} $$ 等級的 attacks。 -
Schnorr signature（Fiat–Shamir in ROM）：
現有 proofs 只能排除 success probability 到 $$ \left(\frac{q_H\cdot t^2}{p}\right)^{1/2} $$ 等級的 attacks，其中 $q_H$ 是 attacker 對 random oracle / hash function 的查詢次數。
之所以 signature 的 bound 會多出 $q_H$，直覺上是因為 reduction 需要在 attacker 的多次 hash queries 中「猜中」那個對應偽造簽章的關鍵查詢點， 因此 tightness 會隨 $q_H$ 變差；而 identification 是互動式 challenge，由 Verifier 隨機給出，沒有 ROM 的查詢數因素。
我們對由具有 special soundness 的 $\Sigma$-protocols 所導出的 identification 與 signature schemes，建立了更 tight 的 security guarantees，特別是對基於 discrete logarithm problem hardness 的 Schnorr schemes。我們透過引入 classic forking lemma 的 high-moment generalization 來 circumvent square-root barrier，並依賴一個假設：底層 relation 是 d-moment hard 的——也就是說，任何 algorithm 在「對一個 random instance 產生 witness」的任務中，其 success probability 會被該 algorithm running time 的第 $d$ 次 moment 所 dominated。
在 discrete logarithm problem 的具體脈絡中，Shoup 的 original proof 已經顯示：在 generic group model 裡，discrete logarithm problem 是 2-moment hard 的。因此，我們的 assumption 可以被視為：在任何目前沒有已知 better-than-generic algorithms 的 group 中，對 discrete logarithm assumption 的一種高度 plausible strengthening。
把我們的 high-moment forking lemma 套用到這個情境後可得：假設 discrete logarithm problem 具有 2-moment hardness，任何 $t$-time attacker 破解 Schnorr identification 與 signature schemes 的機率至多分別為
\[\left(\frac{t^2}{p}\right)^{2/3} \quad\text{以及}\quad \left(\frac{q_H \cdot t^2}{p}\right)^{2/3}.\]The square-root barrier
為了把 Schnorr identification scheme 與 signature scheme 的 security 建立在 discrete logarithm problem 的 hardness 上，必須分別將任何惡意的 impersonator 與任何惡意的 forger 轉換成一個 discrete-logarithm algorithm。既有的方法主要建立在 Pointcheval 與 Stern 的經典 forking lemma 之上 PS00（也可參見 AAB+02, BN06, BCC+16, KMP16 以及其中引用的文獻）。不同方法之間的差異，反映在它們對應的 discrete-logarithm algorithm 之「success probability 與 running time」之間的不同 trade-off。
對於 Schnorr identification scheme，任何在時間 \(t\) 內運行、並以機率 \(\varepsilon\) 破解 scheme security 的惡意 impersonator，例如可以被轉換成一個 discrete-logarithm algorithm：其 success probability 約為 \(\varepsilon^2\)，而 running time 約為 \(t\)。類似地，對於 Schnorr signature scheme，任何在時間 \(t\) 內運行、發出 \(q_H\) 次 random-oracle queries、並以機率 \(\varepsilon\) 破解 scheme security 的惡意 forger，可以被轉換成一個 discrete-logarithm algorithm：其 success probability 約為 \(\varepsilon^2/q_H\)，而 running time 約為 \(t\)。
因此，在任何 order 為 \(p\) 且我們相信 Shoup 的 generic hardness result 對於計算 discrete logarithms 成立的 group 中 Sho97，這會導致對 Schnorr identification scheme 的 bound \(\varepsilon \le \left(\frac{t^2}{p}\right)^{1/2},\) 以及對 Schnorr signature scheme 的 bound \(\varepsilon \le \left(\frac{q_H \cdot t^2}{p}\right)^{1/2}.\)
（我們引導讀者參考 Section 3，了解多年來提出的各式其他 trade-off；如 Bellare 與 Dai 以及 Jaeger 與 Tessaro 近期所觀察到的，這些 trade-off 最終都導致相同的 square-root bounds BD20, JT20。）
然而，在這類 groups 中，對 Schnorr identification 與 signature schemes 的 best-known attack 是透過 discrete-logarithm computation，其 success probability 為 \(t^2/p\)。例如，對一個 256-bit 的 prime \(p\)，best-known 的 \(2^{80}\)-time attack 對 Schnorr identification scheme 的 success probability 約為 \(2^{-96}\)；但 square-root bound 只能排除 success probability 大於 \(2^{-48}\) 的 attacks。（對 Schnorr signature scheme 而言，由於還額外依賴 \(q_H\)，這個 gap 只會更大。）
-
Reduction（從 break 到解 DLP）
forking-based reduction 會把「以機率 $\varepsilon$ break Schnorr」轉換成「解 discrete logarithm」的演算法。
對 Schnorr identification scheme：若有 impersonator 在時間 $t$ 內以機率 $\varepsilon$ 成功，則可構造一個 discrete-logarithm algorithm，其 success probability 約為 $\varepsilon^2$，running time 約為 $t$。
對 Schnorr signature scheme（Fiat–Shamir in ROM）：若有 forger 在時間 $t$ 內、做 $q_H$ 次 random-oracle queries 且以機率 $\varepsilon$ 成功，則可構造一個 discrete-logarithm algorithm，其 success probability 約為 $\varepsilon^2/q_H$，running time 約為 $t$。 -
Shoup generic hardness 與 square-root bounds 的推導關係
Shoup 的 generic hardness result（group order $p$）給出：任何時間 $t$ 的 discrete-logarithm algorithm 的 success probability 受限於 $t^2/p$ 的量級。
將上述 reduction 產生的 DLP success probability 與 Shoup 的上界相對照後，得到對 break 機率 $\varepsilon$ 的限制：
identification：由 $\varepsilon^2 \lesssim t^2/p$ 推得 $$\varepsilon \le \left(\frac{t^2}{p}\right)^{1/2}$$
signature：由 $\varepsilon^2/q_H \lesssim t^2/p$ 推得 $$\varepsilon \le \left(\frac{q_H \cdot t^2}{p}\right)^{1/2}$$ -
square-root barrier 與 best-known attack 的落差
在這類 groups 中，best-known attack 通常直接透過 discrete-logarithm computation，其 success probability 約為 $t^2/p$，與上述證明給出的 square-root 型 bound 存在明顯 gap。
例：256-bit prime $p$，$2^{80}$-time attack 對 identification 的 success probability 約 $2^{-96}$，但 square-root bound 只能排除到約 $2^{-48}$；對 signature 由於還額外依賴 $q_H$，gap 進一步放大。
References
Forking Lemma
- PS00 D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, 2000.
- AAB+02 M. Abdalla, J. H. An, M. Bellare, and C. Namprempre. From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security. In Advances in Cryptology–EUROCRYPT’02, pages 418–433, 2002.
- BN06 M. Bellare and G. Neven. Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma. In ACM CCS, 2006.
- BCC+16 J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Advances in Cryptology–EUROCRYPT’16, pages 327–357, 2016.
- KMP16 E. Kiltz, D. Masny, and J. Pan. Optimal Security Proofs for Signatures from Identification Schemes. In Advances in Cryptology–CRYPTO’16, pages 33–61, 2016.
- 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.
- JT20 J. Jaeger and S. Tessaro. Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness. In Proceedings of the 18th Theory of Cryptography Conference, pages 414–443, 2020.
- Sho97 V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Advances in Cryptology–EUROCRYPT’97, 1997.