將 Schnorr 的辨識方案定量簡化為 DLP
問題
我在 Katz 和 Lindell 的現代密碼學導論（第 3版）（或幾乎等同於 Dan Boneh 和 Victor Shoup 的免費提供的應用密碼學研究生課程）中尋求定理 13.11 的定量更好的證明。證明是關於通用組的 Schnorr 辨識方案 $ \mathcal G $ 素數的 $ q=\lvert\mathcal G\rvert $ 和發電機 $ g\in\mathcal G $ , 對於索賠：
如果離散對數問題相對於 $ \mathcal G $ ，則 Schnorr 辨識方案是安全的。
該計劃如下：
證明者（P）提取私鑰 $ x\gets\mathbb Z_q $ ，計算並發佈公鑰 $ y:=g^x $ , 假設完整性。
在每個標識處：
- 證明者 (P) 平局 $ k\gets\mathbb Z_q $ ，計算並發送 $ I:=g^k $
- 驗證者 (V) 抽取並發送 $ r\gets\mathbb Z_q $
- 證明者 (P) 計算並發送 $ s:=r,x+k\bmod q $
- 驗證者 (V) 檢查是否 $ g^s;y^{-r};\overset?=;I $
給出的證明是對立的。我們假設一個 PPT 算法 $ \mathcal A $ 那，給定 $ y $ 但不是 $ x $ ，以非消失機率成功辨識。我們構造如下的PPT算法 $ \mathcal A’ $ :
- 跑 $ \mathcal A(y) $ ，允許查詢和觀察誠實的成績單 $ (I,r,s) $ ，在到達下一步之前。
- 什麼時候 $ \mathcal A $ 輸出 $ I $ ， 選擇 $ r_1\gets\mathbb Z_q $ 並將其交給 $ \mathcal A $ ，它響應 $ s_1 $ .
- 跑 $ \mathcal A(y) $ 第二次使用相同的隨機磁帶和誠實的成績單，以及何時輸出（相同） $ I $ ， 選擇 $ r_2\gets\mathbb Z_q $ 和 $ r_2\ne r_1 $ 並給 $ r_2 $ 至 $ \mathcal A $ .
最終， $ \mathcal A $ , 回應 $ s_2 $ .
- 計算 $ x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q $ ，解決 DLP。
假設步驟 2 以機率完成 $ \epsilon $ . 我知道這本書的證明確定步驟 3 至少以機率完成 $ \epsilon^2-1/q $ ，為什麼步驟 4 解決了 DLP，為什麼 $ \epsilon^2 $ 出現以及為什麼我們需要一個大 $ q $ 接近那個。
我們能否在數量上對 DLP 做出更令人信服的縮減？
不滿意的地方是： $ \epsilon^2 $ ，這可以轉化為低成功機率。我們希望減少成功機率隨所用時間線性增長的情況，以降低機率。此外，成功的機率是平均所有的 $ y\in\mathcal G $ ，而不是針對特定的 DLP 問題。
使第一個問題具體化：如果 $ \mathcal A $ 以機率成功 $ \epsilon=2^{-20} $ 在 $ 1 $ 其次，證明告訴我們可以解決平均 DLP 機率為 $ 2^{-40} $ 在 $ 2 $ 秒。這不是直接有用的，即使我們可以把它變成機率 $ 1/2 $ 在 $ 2^{40} $ 秒（11 個世紀）。我們想要機率 $ 1/2 $ 在 $ 2^{21} $ 秒（25 天）。
暫定答案
這是我的嘗試，歡迎批評。我聲稱我們可以解決任何特定的 DLP $ G $ 與預期時間 $ 2t/\epsilon $ （並且有機率 $ >4/5 $ 時間內 $ 3t/\epsilon $ )，加上辨識任務的時間，假設一個算法 $ \mathcal A $ 及時辨識隨機公鑰 $ t $ 具有非消失機率 $ \epsilon $ ， 和 $ q $ 足夠大，我們可以折扣在隨機選擇中達到特定值 $ \mathbb Z_q $ .
聲稱的證據：
首先我們建立一個新的算法 $ \mathcal A_0 $ 輸入設置的描述 $ (\mathcal G,g,q) $ 和 $ h\in\mathcal G $
均勻隨機選擇 $ u\gets\mathbb Z_q $
計算 $ y:=h;g^u $
執行算法 $ \mathcal A $ 帶輸入 $ y $ 作為隨機公鑰
每當 $ \mathcal A $ 要求誠實的成績單 $ (I,r,s) $
- 均勻隨機選擇 $ r\gets\mathbb Z_q $ 和 $ s\gets\mathbb Z_q $
- 計算 $ I:=g^s;y^{-r} $
- 供應 $ (I,r,s) $ 至 $ \mathcal A $ ，這與公鑰的誠實記錄不同 $ y $
如果 $ \mathcal A $ 輸出 $ I $ 在其分配的執行時間內 $ t $ , 嘗試進行身份驗證
- （注意：我們將從這裡重新開始）
- 均勻隨機選擇 $ r\gets\mathbb Z_q $ 並將其傳遞給 $ \mathcal A $
- 如果 $ \mathcal A $ 輸出 $ s $ 在其分配的執行時間內 $ t $
- 支票 $ g^s;y^{-r};\overset?=;I $ 如果是，則輸出 $ (u,r,s) $
- 否則，中止沒有結果。
算法 $ \mathcal A_0 $ 是一種 PPT 算法，對於任何固定輸入 $ h\in\mathcal G $ 每次執行機率 $ \epsilon $ 輸出 $ (u,r,s) $ ， 因為 $ \mathcal A $ 在定義的條件下執行 $ \epsilon $ .
我們製作了一個新算法 $ \mathcal A_1 $ 輸入設置 $ (\mathcal G,g,q) $ 和 $ h\in\mathcal G $
- 反復執行 $ \mathcal A_0 $ 用那個輸入直到它輸出 $ (u,r_1,s_1) $ . 每次執行都有機率 $ \epsilon $ 成功，因此這一步預計需要 $ t/\epsilon $ 時間執行 $ \mathcal A $ .
- 重新開始 $ \mathcal A_0 $ 從指定的重新啟動點開始（等效地：使用相同的輸入和隨機磁帶從開始重新執行到重新啟動點，在重新啟動點之後具有新的隨機性），直到它輸出 $ (u,r_2,s_2) $ . 每次執行至少有機率 $ \epsilon $ 成功（證明來自關於我試圖要求參考的算法的非遞減成功機率的定理），因此這一步預計需要不超過 $ t/\epsilon $ 時間執行 $ \mathcal A $ .
- 在（假設極有可能）的情況下 $ r_1\ne r_2 $ , 計算和輸出 $ z:=s_1-s_2-u\bmod q $ .
在那個結果中，兩次執行 $ \mathcal A_0 $ 產生的 $ (u,r_1,s_1) $ 和 $ (u,r_2,s_2) $ 已檢查 $ g^{s_i};y^{-{r_i}}=I $ 和 $ y=h^u $ 對於相同的 $ u $ 和 $ I $ 那 $ \mathcal A_0 $ 確定，並且 $ h $ 我們在輸入時給出 $ \mathcal A_1 $ . 所以 $ \mathcal A_1 $ 成立 $ z $ 和 $ h=g^z $ ，從而解決任意的 DLP $ h $ . 預計執行時間花費在 $ \mathcal A $ 最多是 $ 2t/\epsilon $ ，其餘的使 $ \mathcal O(\log(q)) $ 每次執行的分組操作 $ \mathcal A $ 以及它需要的每一份誠實的成績單。
$ \lfloor3/\epsilon\rfloor $ 執行 $ \mathcal A $ 足以讓他們中的至少兩個成功的機率比 $ 1-4,e^{-3}>4/5 $ ：看到這個情節 $ 1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor,\epsilon,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1} $
$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $
這是我能想到的最嚴格的分析——它使用了分裂引理，但還是決定把它打出來，希望有人會覺得它有用（請隨時指出任何錯誤）。
（下面的分析是針對一個固定的 DLP 實例，但想法可以很容易地擴展。）
分裂引理$$ Lemma 1, PS $$： 讓 $ \sG\subseteq\sR_-\times\sR_+ $ 是這樣的$$ \Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon. $$對於任何 $ \beta<\epsilon $ ， 定義 $$ \sB:=\left{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+’\in\sR_+}[(\rho_-,\rho_+’)\in\sG\right}. $$ 以下持有：
- $ \Pr[\sB|\sG]\geq\beta/\epsilon $ 和
- $ \Pr_{\rho_+’\in\sR_+}[(\rho_-,\rho_+’)\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\beta. $
這裡， $ \sG $ 是一組“好”隨機硬幣，在某種意義上這些硬幣會導致對手成功，並且 $ \sB\subseteq\sG $ 是“更好的”隨機硬幣的子集，因為使用這些硬幣進行倒帶和重播可能會成功。引理的第一個結論是好的硬幣至少在機率上更好 $ \beta/\epsilon $ 第二個結論是，對更好的硬幣進行重新採樣將至少有機率得到一個好的硬幣 $ \epsilon-\beta $ .
歸約的第一部分的分析很簡單：所有的機率 $ 1/\epsilon $ 執行失敗是 $ 1-(1-\epsilon)^{1/\epsilon} $ . 讓我們假設，wlog，最後一次執行成功。讓我們將在倒帶點之前和之後對手在這次執行中使用的硬幣表示為 $ \rho_- $ 和 $ \rho_+ $ ， 分別。根據分裂引理，至少有一次重放成功的機率是 $$ \frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right). $$ 這裡， $ \beta/\epsilon $ 是最後一次執行（我們知道這是好的）更好的機率（結論 $ 1 $ ） 和 $ (\epsilon-\beta) $ 大括號內是更好硬幣的重新採樣導致良好硬幣的機率（結論 $ 2 $ ).
為了優化上面的方程，設置 $ \beta=\epsilon(1-\epsilon) $ （接近 $ \epsilon $ ）。這會產生成功機率 $ (1-\epsilon)(1-(1-\epsilon^2)^{1/\epsilon}) $ .
$$ PS $$: Pointcheval 和 Stern，數字簽名和盲簽名的安全參數，JoC 2000。
讓我試著回答你的問題:)
首先，根據你的描述（我沒有你提到的那本書），這個問題屬於可證明的安全理論。可證明安全性的一般思想是：假設算法/對手A可以以不可忽略的機率e破解基於密碼的方案，那麼模擬器/挑戰者S可以解決數學問題的一個實例，該方案是基於通過與A
**e' <= e**互動，其具有由故障機率確定的不可忽略的機率。更重要的是，安全證明的過程應該基於對手的攻擊遊戲/模型，例如 IND-CPA、EUF-CMA 等，它定義了對手在該特定模型中的能力。所以，我認為你的問題部分給出的證明是基於 EUF-DCMA，而你的答案部分的證明是基於 EUF-CMA。
在模擬器創建的模擬世界中，模擬器可以有一些
super power，通過它可以根據對手的輸出解決現實世界中的一個難題。上述證明中的超能力是所謂的rewind，著名的倒帶模擬引理，可以從對手的輸出中提取秘密值。現在，讓我們看一下原始證明。為了解決 DLP，模擬器將 A倒回到
step 3. 即A執行了兩次，因此成功提取x的機率為 $ e’=e*e=e^2 $ ，因為這是一個連續的事件。此外，在步驟 3 中， $ r_1=r_2 $ 是 $ 1/q $ . 所以，我們還需要減去 $ 1/q $ 確定最終成功的機率 $ e’=e^2-1/q $ .安全證明的過程是一種思想實驗，就像薛定諤的貓（也許不合適），我們沒必要把它放到實際實驗中。我們只需將方案的安全性降低為一個或多個難題就足夠了。
你聲稱的證明過程非常有趣，而且我不知道。有一本很棒的書可以進一步理解可證明的安全性。