Is there a way to prove equality of plaintext that was encrypted using different public keys?
Imagine if Alice encrypts message to Bob (using public key [Math Processing Error] $ P_{bob} $ ) and then Bob encrypts the same message to Carol (using [Math Processing Error] $ P_{carol} $ ). Is there a way for Bob to prove that:
- [Math Processing Error] $ P_{carol} $ was indeed used
- Message is still the same that Alice passed to Bob.
Note1: Both ciphertexts and public keys are visible for everybody who needs to verify this proof. Note2: Public keys and messages are new for every encryption so deterministic encryption is ok, but public key cryptography has to be used
它看起來類似於這個主題，但只使用了一個公鑰： 是否有一個公鑰語義安全的密碼系統可以在零知識的情況下證明兩個明文的等價性？（來自 DW 和 tylo 的評論很有幫助）
- 想到的明顯想法是使用交換加密，所以每個人都可以檢查是否 $ E_{bob}(E_{carol}(M)) == E_{carol}(E_{bob}(M)) $ 有 $ E_{carol}(M) $ 和 $ E_{bob}(M) $ 並訪問 $ P_{bob} $ and [Math Processing Error] $ P_{carol} $ . But then only deterministic encryption would work ([Math Processing Error] $ E_{bob} $ is encryption using [Math Processing Error] $ P_{bob} $ ).
- The other solution that comes to my mind is using ZKP for DH 4-tuple if homomorphic encryption is used (for example El-Gamal - non-interactive proof is described here). So there is a way to prove that ([Math Processing Error] $ g $ , [Math Processing Error] $ h $ , [Math Processing Error] $ g^r $ , [Math Processing Error] $ h^r $ ) is DH 4-tuple (where [Math Processing Error] $ h $ is public key, [Math Processing Error] $ r $ - random number, [Math Processing Error] $ g $ - 組的生成器）。在我們的例子中，與消息[數學處理錯誤]對應的密文是[數學處理錯誤]和 $ M $ $ c_1=(g^{r_1}, MP_{bob}^{r_1}) $ $ c_2=(g^{r_2}, MP_{carol}^{r_2}) $ . 如果考慮到 $ r_1=r_2=r $ （即愛麗絲也告訴鮑勃 $ r_1 $ ) 我們可以劃分 $ c_1 $ 至 $ c_2 $ 並收到 $ (\frac{P_{bob}}{P_{carol}})^r $ . 既然大家都知道 $ P_{bob} $ 和 $ P_{carol} $ , Bob 能夠創建 ZKP $ (g, (\frac{P_{bob}}{P_{carol}}) $ , [數學處理錯誤] , $ g^r $ $ (\frac{P_{bob}}{P_{carol}})^r) $ 是 DH 4 元組。通過這種方式，他可以證明這兩個陳述（我相信:)）可以進行非互動式證明。有[數學處理錯誤]和[數學處理錯誤] Bob 會： $ c_1 $ $ c_2 $
- 選擇隨機[數學處理錯誤] $ r_3 $
- 計算[數學處理誤差]和[數學處理誤差] $ u=g^{r_3} $ $ v=(\frac{P_{bob}}{P_{carol}})^{r_3 } $
- 計算雜湊[數學處理錯誤] $ d = H(u || v) $
- 計算 $ z=d*r+r_3 $
- 發布 $ (u, v, z) $
每個人都可以驗證證明 $ (u, v, z) $ 正在做：
- 計算 $ d = H(u || v) $
- 檢查 $ g^z == (g^r)^d * u $
- $ (\frac{P_{bob}}{P_{carol}})^z ==({\frac{c_1}{c_2}})^d * v $
還有其他方法嗎？
這是在 Elgamal 加密的情況下使用零知識證明對您的問題的回答。這個方案和你自己最大的不同是 Alice 不需要告訴 Bob 的值 $ r_1 $ 了。這使得零知識證明更加複雜。
設置場景：
令[ Math Processing Error ]是發生 Elgamal 加密的素數階[ Math Processing Error ]組。讓 $ \mathbf{G} $ $ p $ $ (g_1,h_1) $ 是 Bob 的公鑰，[ Math Processing Error ]是 Bob 的私鑰，所以[ Math Processing Error ]。讓 $ s_1 $ $ g_1 = h_1^{s_1} $ $ (g_2,h_2) $ 是卡羅爾的公鑰。
讓[ Math Processing Error ]是 Bob 從 Alice 那裡收到的密文。Bob 不知道[數學處理錯誤]，但他知道解密的消息是 $ (c_1,d_1) = (mg_1^{r_1},h_1^{r_1}) $ $ r_1 $ $ m = c_1 d_1^{-s_1} $ .
令[ Math Processing Error ]為 Bob 發送給 Carol 的密文。 $ (c_2,d_2) = (mg_2^{r_2},h_2^{r_2}) $
Bob 將使用零知識證明來證明以下內容，而不會洩露任何關於 $ s_1 $ 和 $ r_2 $ :
$ s_1 $ 是對應的密鑰 $ g_1,h_1 $
$ d_2 = h_2^{r_2} $ ， 意思是 $ r_2 $ 是用於的隨機性 $ (c_2,d_2) $
[數學處理錯誤]，意思是解密得到的消息 $ c_2 = c_1 d_1^{-s_1} g_2^{r_2} $ $ (c_1,d_1) $ 和 $ s_1 $ 和加密的一樣 $ (c_2,d_2) $
零知識證明
證明聲明： $ (c_1,d_1),(c_2,d_2),g_1,h_1,g_2,h_2 $
鮑勃選擇 $ b_1,b_2 $ 均勻隨機地從[數學處理錯誤] [數學處理錯誤] $ \mathbb{Z}_p $ . Bob 計算 $ G_1 = h_1^{b_1} $ , $ G_2 = h_2^{b_2} $ , $ G_3 = d_1^{b_1} g_2^{-b_2} $
Bob 計算雜湊[Math Processing Error] $ x = h(proof statement || G_1 || G_2 || G_3) $ （我認為也有必要在您的原始範例中包含該語句，但需要檢查）。
Bob 計算[Math Processing Error] $ \bar{s}_1 = s_1 x + b_1 $ 和[Math Processing Error] $ \bar{r}_2 = r_2 x + b_2 $ .
鮑勃發布[Math Processing Error] $ (G_1,G_2,G_3,\bar{s}_1,\bar{r}_2) $ .
確認：
為了驗證，首先計算[Math Processing Error] $ x = h(proof statement || G_1 || G_2 || G_3) $ .
檢查[Math Processing Error] $ h_1^{\bar{s}_1} = g_1^x G_1 $ （顯示[Math Processing Error] $ \bar{s}_1 $ 是 Bob 公鑰的隨機版本）
檢查[數學處理錯誤] $ h_2^{\bar{r}_2}=d_2^x G_2 $ （顯示 $ \bar{r}_2 $ 是使用的隨機性 $ (c_2,d_2) $ )
檢查 $ c_2^x c_1^{-x} d_1^{\bar{s}_1} g_2^{-\bar{r}_2} = G_3 $ （表明兩個密文中的消息是相同的）
安全證明草圖：
我將繪製一個證明，證明驗證者隨機選擇的底層互動式 ZKP $ x $ 從 $ \mathbb{Z}_p $ 是安全的，然後依靠眾所周知的事實，即用雜湊替換它以獲得上述內容，從而提供安全的 NIZK 協議將完全零知識。
（完整性）很容易看出，誠實的證明者總是會通過替換誠實計算的值來說服驗證者 $ \bar{s}_1,\bar{r}_2,G_1,G_2,G_3,x $ 進入驗證方程。
（特別健全）同樣 $ G_1,G_2,G_3 $ ，如果證明者可以產生可接受的證明 $ \bar{s}_1,\bar{r}_2 $ 和 $ \bar{s}’_1,\bar{r}’_2 $ , 對於兩個不同的值 $ x,x’ $ ，然後我們可以提取 Bob 的密鑰（以及消息），以及第二個密文中使用的隨機性。從第一個驗證方程，我們可以計算 $ s_1,b_1 $ , 的離散對數 $ g_1,G_1 $ 關於 $ h_1 $ , 這樣 $ \bar{s}_1 = s_1 x + b_1 $ 同樣對於 $ \bar{s}’_1 $ . 從第二個方程，我們可以計算 $ r_2,b_2 $ , 的離散對數 $ d_2,G_2 $ 關於[Math Processing Error] $ h_2 $ , 這樣[Math Processing Error] $ \bar{r}_2 = r_2 x + b_2 $ , 同樣對於[Math Processing Error] $ \bar{r}’_2 $ . 代入第三個驗證方程，我們有[Math Processing Error] $ \left( c_2 c_1^{-1} d_1^{s_1} g_2^{-r_2} \right)^x d_1^{b_1} g_2^{-b_2} = G_3 $ . 這是一個多項式（在組元素中），它滿足兩個不同的值[Math Processing Error] $ x $ 和[Math Processing Error] $ x’ $ ，所以所有係數必須等於組標識。取係數[Math Processing Error] $ x $ , 我們有[Math Processing Error] $ c_2 = c_1 d_1^{-s_1} g_2^{r_2} $ . 換句話說，第一個密文的解密，當加密時，給出了第二個密文。
（特殊誠實驗證者零知識）給出[Math Processing Error] $ x $ ，模擬器可以選擇[Math Processing Error] $ \bar{s}_1,\bar{r}_2 $ 均勻隨機地從[Math Processing Error] $ \mathbb{Z}_p $ ，然後計算 $ G_1,G_2,G_3 $ 使用驗證方程。
一種想法是使用普通的混合加密。Bob 可以重用對稱密文並使用 Carol 的公鑰再次加密對稱密鑰（材料）。如果在對稱部分正確選擇了身份驗證，Bob 將無法找到另一個密鑰來正確地將密文解密為其他消息。例如，假設散列函式是安全的，HMAC 就有這個屬性。
任何人都可以比較密文的對稱加密部分，如果它們相同，則消息（如果可解密）是相同的。
請注意限制：其他人無法證明 Bob 確實為 Carol 加密了正確的密鑰。只有 Carol 能夠檢查這一點，因此消息可能根本不會解密。或者實際上會正確解密，但使用其他人的密鑰。
為了讓其他人也能夠驗證所有內容，您可以對公鑰加密部分使用交換算法。混合加密的使用避免了整個方案具有確定性的需要，因為 Alice 可以（並且應該）使用隨機對稱密鑰。