攻擊 ElGamal 一種變體的對手
我來了以下問題：
考慮以下 ElGamal 加密的變體。讓 $ p= 2q+ 1 $ ， 讓 $ G $ 是模平方群 $ p $ 所以 $ G $ 是一個子群 $ Z_p^* $ 有秩序的 $ q $ ， 然後讓 $ g $ 成為 $ G $ . 私鑰是 $ (G, q, g, x) $ 公鑰是 $ (G, q, g, h) $ ， 在哪裡 $ h = > g^x $ 和 $ x\in Z_q $ 是統一選擇的。加密消息 $ m ∈ > Z_q $ , 選擇制服 $ r∈Z_q $ , 計算 $ c_1=g^r $ 反對 $ p $ 和 $ c2=h^r+m $ 反對 $ p $ , 並設密文為 $ (c_1, c_2) $ . 這個方案是 CPA 安全的嗎？證明你的答案。
這裡 $ G $ 是所有元素的集合 $ Z_p^* $ 這是二次餘數模 $ p $ 和 $ Z_p^* \setminus G $ 是一組非二次剩餘元素。我認為攻擊者應該選擇兩條消息，其中一個加密是在集合二次剩餘模中 $ p $ IE $ G $ 一個在非二次殘差集中，即 $ Z_p^* \setminus G $ 然後使用這個屬性來區分挑戰密文。例如，如果攻擊者選擇 $ m_0 = 0 $ 的加密 $ m_0 $ 將在集合二次殘差模中 $ p $ IE $ G $ .
攻擊者應該如何選擇 $ m_1 $ 能準確計算出對手的優勢嗎？攻擊者可以選擇 $ m_1 $ 均勻且以良好的機率加密它不會在集合二次殘差中，但我無法計算該攻擊者的確切優勢。我想要一個攻擊者，我可以計算出確切的優勢。
我們也知道 $ |G| = |Z_p^* \setminus G | = q $ 但我們不知道元素的方式 $ G $ 分佈在 $ Z_p^* $ .
**回想一下：**很容易判斷一個元素是否 $ g∈Z_p^∗ $ 是二次餘數（只要看看 $ g^q= 1 $ 模式 p)。
攻擊者應該如何選擇 $ m_1 $ 能準確計算出對手的優勢嗎？
那麼，對於 $ p $ 素數，那麼正好 $ q $ 中的值 $ (1, p-1) $ 將是二次殘差和精確的 $ q $ 不會是; 此外，還有一個值（ $ 0 $ ) 位於組之外（因此也是一個不可能的值 $ h^r $ ）。因此，如果他選擇 $ m_1 $ 均勻地從範圍 $ (0, p-1) $ （並且獨立於值 $ r $ 加密器選擇），然後 $ h^r + m_1 $ 將是范圍內均勻的隨機值 $ (0, p-1) $ ，因此將是二次非殘差或機率為 0 $ (q+1)/p > 0.5 $ .
您應該能夠從中精確計算出優勢。
@poncho 的答案並不是我的問題的確切解決方案，因此 StackExchange 規則建議我添加我的答案，這可能對某人有所幫助。
我們構造攻擊者如下。攻擊者給出 $ m_0 = 0 $ 和 $ m_1 $ 從 $ \mathbb{Z}_q $ 給挑戰者並獲得挑戰密文 $ c $ . 如果 $ c $ 是二次剩餘然後攻擊者返回 $ b = 0 $ 否則返回 $ b = 1 $ . 這種攻擊者的優勢是 $$ Adv \geq \frac{1}{2} * 1 + \frac{1}{2} * \frac{q-1}{2q} = \frac{3q-1}{4q} . $$ 因此，我們建構了一個具有不可忽略優勢的攻擊者，這表明該方案不是 CPA 安全的。