證明 Schnorr 簽名方案的安全性
我知道 Schnorr 的簽名很重要，因為它是最緊湊的簽名方案之一，其安全性已在隨機預言模型中得到證明。
現在，我想知道這樣的證明是否容易，有人可以向我解釋，或者只是指出證明的主要步驟。
為了清楚起見，我知道的 Schnorr 簽名方案是維基百科頁面Schnorr signature提出的方案：
- 選擇參數：方案的所有使用者都同意一個組 $ G $ 素數的 $ q $ ，其中 DLP 很難（例如 $ G $ 是Schnorr Group或素數階橢圓曲線 $ q $ )，生成器 $ g \in G $ , 並在雜湊函式上 $ H:{ 0,1 }^* \rightarrow \mathbb{Z}_q $
- 密鑰生成：簽名者選擇一個密鑰 $ x \in \mathbb{Z}_q $ 並使 $ y=g^x $ 上市。
- 簽名：簽署消息 $ M $ ，簽名者隨機選擇一個 $ k \in \mathbb{Z}_q - { 0 } $ , 計算 $ r=g^k $ ， 讓我們 $ e=H(M||r) $ , 並讓 $ s=k-xe $ . 簽名的消息是 $ (M,(s,e)) $ .
- 驗證：任何人都可以驗證 $ (s,e) $ 是一個簽名 $ M $ 通過計算 $ r_v = g^s y^e $ 和 $ e_v = H(r_v||M) $ ; 如果 $ e_v = e $ 簽名得到驗證。
現在，正確性證明非常簡單（即，如果一個人遵循協議，那麼驗證方程 $ e_v = e $ 成立），但我不知道如何正式證明安全性（即，如果一個人不遵循協議，則驗證方程不太可能成立，因此很難在不知道的情況下在消息上偽造簽名密鑰）。
任何提示或建議的讀數將不勝感激！
Pointcheval 和 Stern
$$ PS00 $$證明了 Schnorr 簽名在隨機預言機模型中的選擇消息攻擊 ( EU-CMA )下是存在不可偽造的，假設離散對數問題 $ ^1 $ (DLP) 很難。 在高層次上，減少（從 DLP 到 Schnorr 簽名的 EU-CMA 安全性）的工作原理如下。約簡算法 $ \mathcal{B} $ 嵌入其 DLP 挑戰 $ g^\alpha $ 進入公鑰（即，集 $ y=g^\alpha $ ) 然後使用oracle-replay 攻擊從偽造者那裡獲取 $ \mathcal{F} $ , 兩個共享簽名隨機性的不同偽造品 ( $ r=g^k $ ）。這使 $ \mathcal{B} $ 解決 $ \alpha $ .
為簡單起見，讓我們首先關註一個較弱的模型，稱為無消息攻擊下的存在偽造( EU-NMA ) 和一個始終成功的*強偽造者。*我們證明了一個強大的偽造者 $ \mathcal{F} $ 最多打破 EU-NMA 模型中的 Schnorr 簽名 $ q $ 對隨機預言機的查詢 $ H $ （即，一個 $ (1,q) $ -adversary) 可用於以機率破壞 DLP $ 1/q $ .
這需要兩輪模擬：
- 第1輪。 $ \mathcal{B} $ 執行 $ \mathcal{F} $ 上 $ (G,g,g^\alpha) $ ; 隨機預言機 $ H $ 以標準方式進行模擬（即惰性採樣加上表格以確保一致性）。在本輪結束時 $ \mathcal{F} $ 返回偽造品 $ (M_0^,(s_0^,e_0^)) $ 在哪裡 $ e_0^=H(M_0^|r_0^) $ . 為簡單起見，假設 $ \mathcal{F} $ 進行了隨機的預言機查詢 $ H(M_0^|r_0^) $ .
- 第 2 輪。現在 $ \mathcal{B} $ 倒帶 $ \mathcal{F} $ 到了它進行隨機預言機查詢的地步 $ H(M_0^|r_0^) $ 在第 1 輪（“關鍵”點）並重新執行 $ \mathcal{F} $ 但獨立於前一輪迴答新的隨機預言機查詢。 $ ^2 $ 這構成了 oracle-replay 攻擊。在第 2 輪結束時， $ \mathcal{F} $ 返回偽造品 $ (M_1^,(s_1^,e_1^)) $ 在哪裡 $ e_1^=H(M_1^|r_1^) $ .
有一個不可忽略的機率（至少 $ 1/q $ ，但這必須嚴格論證）在第 2 輪中也是如此 $ \mathcal{F} $ 在臨界點鍛造（即， $ M_1^=M_0^ $ 和 $ r_1^=r_0^ $ ) 但是對隨機預言機查詢的響應 $ H(M_0^|r_0^) $ 是不同的（即， $ e_1^\neq e_0^ $ ）。直覺的原因是 $ \mathcal{F} $ 必須偽造一些查詢，在最壞的情況下，它會隨機選擇這一點。如果確實如此，那麼
$$ s_0^=k_0^-\alpha e_0^* \text{ and } s_1^=k_0^-\alpha e_1^, $$ （作為 $ r_1^=r_0^* $ ， 但 $ e_1^\neq e_0^ $ ） 和 $ \mathcal{B} $ 可以解決 $ \alpha $ $$ \alpha=\frac{s_1^-s_0^}{e_0^-e_1^}. $$ 可以加強上述論點以適應一般 $ (\epsilon,q) $ -EU-CMA 模型中的對手。為了模擬簽名預言機（對於 EU-CMA 模型），減少只需對隨機預言機進行適當的程式。 $ ^3 $ . 限制一般對手減少的成功機率（即以不可忽略的機率成功） $ \epsilon $ ) 是相當技術性的並且使用所謂的分叉引理。準確地說，如圖所示
$$ PS00 $$那一個 $ (\epsilon,q) $ -鍛工 $ \mathcal{F} $ 破壞 EU-CMA 模型中的 Schnorr 簽名可用於以機率破壞 DLP $ O(\epsilon^2/q) $ . $ ^4 $ 腳註。
$ ^1 $ 循環群上的 DLP $ (G,g,q) $ 需要找到 $ \alpha\in\mathbb{Z}_q $ 給定 $ g^\alpha\in G $ .
$ ^2 $ 也就是說，直到關鍵點的查詢得到一致的回答，但在關鍵點之後的新查詢獨立於第 1 輪得到回答。
$ ^3 $ 為消息生成簽名 $ M $ ， 選擇 $ e,k\in_R\mathbb{Z}_q $ ， 放 $ r=(g^\alpha)^e\cdot g^k $ , 並對隨機預言機進行程式以設置 $ H(M|r)=e $ . 返回 $ (M,(e,k)) $ 作為簽名。不難看出該消息是有效的，並且來自正確的分發。
$ ^4 $ 後來出現在一系列作品中
$$ PV05,GBL08,Seu12 $$損失是緊度 $ \epsilon/q $ 是固有的（條件是假設所謂的多一個離散對數是困難的）。 參考。
$$ PS00 $$大衛 Pointcheval 和雅克斯特恩。數字簽名和盲簽名的安全參數。密碼學雜誌，2000 年。
$$ PV05 $$帕斯卡 Paillier 和 Damien Vergnaud。基於離散對數的簽名可能不等同於離散對數。亞洲密碼 2005。
$$ GBL08 $$Sanjam Garg、Raghav Bhaskar 和 Satyanarayana V. Lokam。改進了基於離散日誌的簽名的安全性降低界限。加密貨幣 2008。
$$ Seu12 $$亞尼希·塞林。關於隨機 Oracle 模型中 Schnorr 類型簽名的精確安全性。2012 年歐洲密碼。
作為@Occams_Trimmer 有用答案的替代方案：
通過結合Katz 和 Lindell 書中的 Theorem 12.10 和 12.11 可以獲得這個事實的更簡單的證明。
這些作者首先給出了3-move 協議的通用Fiat-Shamir 變換。然後它只表明互動式Schnorr“辨識方案”是安全的，這更容易做到。總結一下：
定理 12.10 ($$ KL15 $$) . 讓 $ \Pi $ 是一個辨識方案，並且讓 $ \Pi’ $ 是通過對其應用 Fiat-Shamir 變換得到的簽名方案。如果 $ \Pi $ 安全且 $ H $ 被建模為隨機預言機，那麼 $ \Pi’ $ 是安全的。
定理 12.11 ($$ KL15 $$) . 如果離散對數問題相對於 $ \mathcal{G} $ ，則 Schnorr 辨識方案是安全的。
請參閱 Katz 和 Lindell 以獲取證明和定義，例如，“辨識方案”“安全”意味著什麼。