兩組之間的 CDH 意味著 El-Gamal 的弱點
讓 $ G $ 素數循環群 $ p $ 帶發電機 $ g $ .
讓 $ H $ 素數循環群 $ p $ 帶發電機 $ h $ .
假設你有一個算法 $ \mathcal{A} $ 給定兩個元素 $ g^a $ 和 $ g^b $ 在 $ G $ 輸出 $ h^{ab} $ 在群裡 $ H $ .
證明 El-Gamal 加密在ciphertext-indistinguishabiliy的意義上是不安全的。
讓 $ a $ 密鑰和 $ (g,g^a) $ 公鑰。
我觀察到如果我們能控制 $ H $ ，我們可以取 $ H=G $ 和 $ h=g^a $ 我們實際上可以使用 $ \mathcal{A} $ .
所以，給定一個加密 $ (g^b,g^{ab}m) $ 我們可以跑 $ \mathcal{A}(g,g^b)=h^{1\cdot b}=(g^a)^b=g^{ab} $ 並且使用它我們可以很容易地獲得 $ m $ .
我的問題
如果我們無法控制 $ H $ 還有可能嗎？我們可以用群同構來證明我們可以調整嗎 $ \mathcal{A} $ 處理我們的選擇 $ H $ ? 或者我們可以使用 $ \mathcal{A} $ 只破解密文不可區分而不是完全解密消息？
你實際上很接近。
因為我不確定我是否理解所述的安全概念，所以我將打破 IND-CPA 安全性，你應該能夠適應這個想法。
讓 $ m_0,m_1 $ 成為我們的挑戰資訊 $ m_0\neq m_1 $ . 讓 $ (g,g^a) $ 成為公鑰， $ a $ 是私鑰和 $ (c_1=g^k,c_2=g^{ak}m_b) $ 成為挑戰密文。讓 $ \mathcal O:G^2\to H:\mathcal O(g^a,g^b)\mapsto h^{ab} $ . 認為 $ h $ 被知道或被定義為 $ \mathcal O(g,g) $ .
我們將使用 $ \mathcal O $ 為 G 組建構一個決策 Diffie-Hellman (DDH) 預言機。由於 ElGamal 的 IND-CPA 安全性只能簡化為 DDH 而不是 CDH，因此破壞 DDH 足以破壞 IND-CPA 安全性。
讓 $ h^a=\mathcal O(g,g^a) $ 和 $ h^b=\mathcal O(g,g^k) $ . 進一步讓 $ h^{ak}=\mathcal O(g^a,g^k) $ . 下一次計算 $ c’=c_2/m_0 $ . 返回 0 如果 $ \mathcal O(g,c’)=h^{ak} $ 否則返回 1 作為挑戰位的猜測 $ b $ .
那麼為什麼會這樣呢？注意如何 $ c’=g^{ak}m_b/m_0 $ 這是 $ g^{ak} $ 如果 $ b=0 $ 和其他的東西。現在 $ \mathcal O(g,c’) $ 將此發送到 $ h^{ak} $ 當且當 $ b=0 $ , 但正如我們已經計算過的 $ h^{ak} $ 使用公鑰，我們現在可以進行比較以驗證我們的猜測 $ m_0 $ !