Discrete-Logarithm

schnorr辨識方案的安全證明

  • May 9, 2021

我研究了 Schnorr 辨識方案,並且遇到了安全證明。

我的問題是關於以下內容: $$ \begin{align} \text{Pr}\left[\text{DLog}{\mathcal{A}’,\mathcal{G}}\left(n\right)=1\right] &= \text{Pr}{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right)\wedge r_1\neq r_2 \right] \ &\geq \text{Pr}{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right) \right]- \text{Pr}{\omega,r_1,r_2}\left[r_1=r_2\right] \ &= \sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \left(\delta_\omega\right)^2}- 1/q \ &\geq \left(\sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \delta_\omega}\right )^2 -1/q \ &= \delta\left(n\right)^2-1/q \end{align} $$

和 $ \delta_\omega \stackrel{def}{=} \text{Pr}_r\left[V\left(\omega,r\right)=1\right] $ 是對手在辨識實驗中成功的機率,假設我們使用 $ \omega $ (隨機選擇)和 $ r $ (挑戰)。

當我們從第 2 行移動到第 3 行時,我們假設對手正確響應挑戰的事件 $ r_1 $ 獨立於對手正確響應挑戰的事件 $ r_2 $ .

但是,我們不知道如何 $ \mathcal{A} $ 正在行動——那麼我們怎麼能假設這些事件是獨立的呢?

我相信這是 Schoor 辨識安全證明的“倒帶引理”部分,並且在 Boneh 和 Shoup 的書“應用密碼學研究生課程”第 727-728 頁中得到了很好的解釋。

這裡的一個重要方面是我們必須考慮另一個對手 B,他模仿(獲取 A 的數字編譯版本)並與 A 進行遊戲/互動。(我們可以將 B 視為想要破壞計劃的任何人,並假設存在一):

  1. 首先,B扮演驗證者的角色,並期望A(扮演證明者的角色)發送w;
  2. B發送r1,等待A的答复;
  3. B倒帶A,使 A 的內部狀態與步驟 1 結束時完全相同;
  4. B發送一個隨機且獨立的r2;等待答案A。

所以 B 可能對 A 的工作方式一無所知,但她/他是給 A 設置獨立挑戰/答案並利用它的人。

引用自:https://crypto.stackexchange.com/questions/89867