密碼隨機化的 NIZK 證明
是否可以簽訂 NIZK 證明密碼是隨機化的？
假設 Alice 創建了一個密碼 $ c = \text{Enc}(m,r) $ 和 ZK 證明 $ c $ 正確形成（例如， $ \text{Enc} $ 可能是解除的 ElGamal 加密函式）。Bob 想要隨機化 $ c $ 並建構 $ c’ = c\cdot \text{Enc}(0,r’) $ . Bob如何證明 $ c’ $ 確實計算正確？
謝謝！
有一種使用離散對數相等證明和 ElGamal 加密的非常簡單的方法。讓我首先回顧一下離散對數等式的以下 sigma 證明：
讓 $ G $ 是一個素數階群，令 $ (a,b,c,d)\in G^4 $ 使得存在 $ x $ 這樣 $ a^x=c $ 和 $ b^x=d $ . 讓一個知道的證明者 $ x $ 並且想要向驗證者證明 $ \log_a(c) = \log_b(d) $
- 證明者選擇 $ r $ 併計算 $ A=a^r $ 和 $ B=b^r $ ，然後他發送 $ (A,B) $ 給驗證者。
- 驗證者隨機選擇一個 $ e $ 並將其發送給證明者。為了將其變成非互動式證明， $ e $ 可以從雜湊生成 $ H(a||b||c||d||A||B) $ 在隨機預言機模型中。
- 證明者返回 $ z= r + xe $ 給驗證者。
- 驗證者檢查 $ a^z=Ac^e $ 和 $ b^z=Bd^e $ .
那麼，我們接下來展示如何使用這個證明來證明一些密文 $ c’ $ 是隨機化 $ c $ .
我們表示 $ g $ 素數階群的生成器 $ G $ ， 經過 $ {\sf pk} \in G $ 公鑰，並通過 $ m\in G $ 明文消息。
我們解析 $ c $ 作為 $ (c_1,c_2)=(g^r,{\sf pk}^r m) $ .
隨機化 $ c $ , Bob 選擇 $ s $ 隨機併計算 $ c’=(c’_1,c’_2)=(c_1 g^s , c_2 {\sf pk} ^s) = (g^{r+s},{\sf pk}^{r+s} m) $ .
為了證明 $ c’ $ 是隨機化 $ c $ , 他證明 $ \log_g(\frac{c’1}{c_1}) = \log{\sf pk}(\frac{c’_2}{c_2}) $ 使用秘密 $ s $ .
請注意，這是有效的，因為 $ \frac{c’_1}{c_1}=g^s $ 和 $ \frac{c’_2}{c_2}={\sf pk}^s $ 具有相同的離散對數 $ s $ 如果密文被正確隨機化。
是的，在這種情況下可以使用 NIZK 證明。
實際上，重新隨機化並證明您已正確完成計算是 NIZK shuffle 協議中的必要步驟之一。在 shuffle 協議中，你會得到一堆密文 $ c_1, c_2, \cdots ,c_n $ 並隨機播放（置換+重新隨機化）它們並輸出 $ c_1’, c_2’, \cdots ,c_n’ $ 這應該是輸入密文的重新隨機化和置換版本。
有關此類證明的更多詳細資訊，我建議查看用於洗牌的 NIZK 證明，其中還包含用於重新隨機化密文的 NIZK。您可以在https://eprint.iacr.org/2017/894或https://eprint.iacr.org/2016/866等文獻中找到一些 NIZK 洗牌證明。