這是兩個paillier加密相等的安全零知識證明嗎？
我們有加密 $ c_1 $ 和 $ c_2 $ ，知道明文和隨機性的人想證明他們知道。讓 $ r_1 $ 和 $ r_2 $ 是隨機值 $ c_1 $ 和 $ c_2 $ 分別。然後證明者隨機生成另一個隨機數， $ z $ . 然後他們計算 $ a_1 = r_1^n z^n $ , $ a_2 = r_2^n z^n $ . 這些就是證據。驗證者只需乘以 $ a_2 $ 和 $ c_1 $ 和 $ a_1 $ 和 $ c_2 $ 並檢查產品是否相等。如果是，那麼可以安全地假設 $ c_1 $ 和 $ c_2 $ 包含相同的秘密。如果 $ a_1 $ 是 $ c_2 $ 和 $ a_2 $ 是 $ c_1 $ 那麼儘管等式為真，但證明顯然是錯誤的。
這是非常不安全的。任何人都可以提供兩個密文等價的假證明。
給定 $ c_1 $ 和 $ c_2 $ , 隨機選擇 $ x $ 然後讓 $ a_1=c_1x\mod {n^2} $ 和 $ a_2=c_2x\mod {n^2} $ . 我們看到 $ a_1c_2\equiv a_2c_1\pmod {n^2} $ 符合驗證標準。
一個證明 $ c_1 $ 和 $ c_2 $ 是相同值的加密等價於表明 $ c_1/c_2\pmod{n^2} $ 是一個 $ n $ 權力。這是一個 sigma 協議，用於證明您可以與通常的 Fiat-Shamir schtick 進行非互動。
為了證明 $ k $ 是一個 $ n $ 次冪模 $ n^2 $
我們假設證明者俱有 $ s:k\equiv s^n\pmod{n^2} $ .
承諾
證明者生成一個統一的隨機數 $ r\mod{n^2} $ , 計算 $ c=r^n\mod{n^2} $ 並發表 $ c $ .
挑戰
驗證者請求證明者發布 $ r $ 這樣 $ r^n=c\mod{n^2} $ 或者 $ r’ $ 這樣 $ r’^n=ck\mod{n^2} $ .
回复
Prover 發布 $ r $ 或者 $ r’=rs\mod{n^2} $ 根據挑戰。
如果響應者可以使用兩種可能的響應，那麼響應者就會知道 $ s=r’/r $ 因此，對這兩種反應的了解證明了 $ s $ . 因此，隨著協議迭代次數的增加，協議正確的機率很高。
Verifer 可以通過首先選擇挑戰，然後是響應，然後是承諾來為自己生成隨機協議轉錄本。因此該協議是零知識的。