重新加密消息並證明消息沒有改變
是否有一種方法允許重新加密消息,以允許只能訪問兩個密文的觀察者證明明文消息在每個密文中是相同的?
更具體地說:如果我有消息 $ m $ ,然後我使用非對稱密鑰方案對其進行加密 $ E_1: c_1 = E_1(m) $ 然後用新的密鑰對重新加密 $ E_2: c_2 = E_2(m), $
有沒有辦法讓只能訪問的觀察者(可能使用 ZKP 或同態加密) $ c_1, c_2 $ 和公鑰 $ E_1 $ 和 $ E_2 $ 來證明 $ m $ 是用於生成的相同純文字 $ C_1 $ 和 $ C_2 $ ?
如果我們假設重加密者是合作的,即他有意識地生成重加密後的密文使這個證明變得容易,那麼這是可能的。
背景:
在 El Gamal 中,生成消息的加密 $ M $ 到公鑰 $ aG $ , 你隨機選擇一個 $ r $ , 並輸出對 $ rG, r(aG) + M $ ; 解密者知道 $ a $ ,因此計算 $ a(rG) = r(aG) $ ,讓他恢復 $ M $ .
配對友好曲線是具有高效可計算函式的橢圓曲線 $ e(A, B) $ 具有以下屬性:
- $ e(aG, bG) = e(G, G)^{ab} $ (對於任何整數 $ a, b $ ,取冪在某個群上,通常是某個有限域的乘法群
- $ e(G,G) \ne 1 $ (這意味著 $ e(G, aG) = 1 $ 當且當 $ a \equiv 0 \pmod q $ , 在哪裡 $ q $ 是素數曲線階數)
$$ END OF BACKGROUND $$ 現在,我對標準 ElGamal 所做的一項修改是在實際消息之間進行隨機可逆映射 $ m $ 和重點 $ X $ 我們實際上是加密的;也就是有一個函式 $ H(m, r) $ ,它接受一條消息 $ m $ , 和一個隨機值 $ r $ , 並輸出一個點 $ X $ ; 有一個反函式需要 $ X $ 並恢復原件 $ m $ . 這是防止攻擊者使用該功能所必需的 $ e $ 測試特定的密文是否對應於特定的明文。
好的,消息的加密 $ m $ 到公鑰 $ A = aG $ 是:
$$ (rG, rA + H(m, r’)) $$
在哪裡 $ r, r’ $ 是隨機值。解密器(誰知道 $ a $ ) 可以恢復 $ m $ 以明顯的方式。
現在,如果加密者決定將兩個密文發送到兩個不同的公鑰,可以由第三方測試為相同,他使用相同的 $ r, r’ $ 價值觀。
然後,當這個第三方收到這兩個密文時:
$ (X, Y) $ 到公鑰 $ A $
$ (W, Z) $ 到公鑰 $ B $
他首先檢查是否 $ X = W $ (如果加密器正在合作,則應該是這種情況;密文的第一個元素不依賴於公鑰。
如果通過,他將檢查是否:
$$ e( G, Y-Z ) = e( X, A-B) $$
這是它的工作原理:
- $ X = rG $ , 在哪裡 $ r $ 是加密器為兩個密文選擇的隨機值
- $ Y = rA + H(x, r’) $ 和 $ Z = rB + H(x’, r") $ , 在哪裡 $ x, x’ $ 是兩個明文。
所以,我們有
$ e(X, A-B) = e(rG, A-B) = e(G,A-B)^r $
$ e(G, Y-Z) = e(G, rA + H(x, r’) - rB - H(x’, r")) = \ e(G,A-B)^{r} \cdot e(G,H(x, r’) - H(x’, r")) $
這兩個將是相同的 $ H(x, r’) = H(x’, r") $ ,也就是說,如果 $ x = x’ $ .