Tight Bounds on Uniform-Challenge Reductions from Sigma Protocols via Hitting Games
Abstract
Sigma protocols 是密碼學中的基礎工具，也是許多實用方案的重要基石；其中最著名的例子包括 Schnorr identification scheme 與 Schnorr signature scheme。為了證明 Sigma protocols 的安全性，作者考慮把「攻破某個 Sigma protocol」這件事 reduce 成「解決某個被假設為困難的問題」，例如在某個群上計算 discrete logarithm。
然而，在許多情況下，這類 reduction 並不是 tight 的：如果存在一個 adversary 能以機率 $\varepsilon$ 攻破某個 Sigma protocol，則該 reduction 往往只能構造出一個以機率 $\varepsilon^2$ 解決底層困難問題的演算法。這種二次損失會影響效率，因為若要達到相同的安全等級，系統就必須選擇更大的 security parameters。
本文證明，對兩類自然的 reductions 而言，這種 quadratic loss 其實是內在且不可避免的。對 interactive protocols，作者針對 uniform-challenge black-box reductions 建立了這個下界；這類 reductions 會用均勻隨機抽樣的 challenges 去查詢 adversary。對 non-interactive protocols，也就是 random oracle model 中的情形，作者則針對 weakly programmable black-box reductions 證明了相同的結論；這類 reductions 會以均勻隨機抽樣的輸出來回答 adversary 的 oracle queries。
作者進一步將這些 lower bounds 應用到從 Schnorr identification 與 Schnorr signatures 到 discrete logarithm 的 reductions 上，得到的下界恰好與既有的正面結果相吻合，也就是 PS00 中的經典 worst-case reduction，以及 RS24 提出的 higher-moment reduction。
本文的核心方法，是把這類 reductions 的分析轉化為一些簡單 hitting games 的數值分析；這些 hitting games 是作者引入的一類組合性遊戲。對這些遊戲建立界限，是本文最主要的技術貢獻。作者也指出，這些界限能讓相關結果的證明方式變得更加模組化。
Introduction
Sigma protocols 是密碼學中的基礎工具，代表性的例子包括 Schnorr identification scheme 與 Schnorr signature scheme。對這類協定進行安全性證明時，典型做法是把攻擊協定的能力 reduction 成解決某個被假設為困難的數學問題，例如 discrete logarithm。
這類 reduction 往往不是 tight 的：若某個 adversary 能以機率 $\varepsilon$ 攻破一個 Sigma protocol，reduction 常只能構造出一個以大約 $\varepsilon^2$ 機率解出底層 hard problem 的演算法。這種 quadratic loss 會削弱 concrete security，因而迫使系統選擇更大的 security parameters。
相關情況大致可分為兩類：一類是 interactive protocols，其中 adversary 接收由 verifier 或 reduction 給出的 challenge；另一類是 non-interactive protocols，也就是 random oracle model 下的情形，其中 adversary 透過 oracle queries 取得對應輸出。對這兩類協定而言，reduction 的 tightness 都是安全性分析中的核心問題。
Our Results
- Introduction
- Preliminaries
- 說明為 互動式 與 非互動式 Sigma Protocol 的 uniform-query reductions 所設計的模擬器（emulator）。
- 引入數個 hitting games，並結合第 5 節所證明的其數值界限，以及第 3 節的結果，進一步對 uniform-query reductions 的品質給出上界。
- 證明第 4 節所提出的 hitting games 的上下界。
References
- PS00 David Pointcheval and Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures. In: Journal of Cryptology 13.3 (June 2000), pp. 361–396. doi: 10.1007/s001450010003.
- RS24 Lior Rotem and Gil Segev. Tighter Security for Schnorr Identification and Signatures: A High-Moment Forking Lemma for Σ-Protocols. In: Journal of Cryptology 37.3 (July 2024), p. 26. doi: 10.1007/s00145-024-09506-5.