Encryption
ElGamal加密中的XOR而不是乘法
在 ElGamal 加密方案中，消息 $ m $ 乘以秘密 $ g^{xy} $ 維基百科。我不明白它的好處。為什麼我們不能用共享的秘密異或我們的消息？據我所知，乘法比 XOR 操作更昂貴。此外，這兩種方案都是 CPA 安全的，但不是 CCA 安全的，在這種情況下，無論如何我們都必須添加 MAC。誰能給我解釋一下？
一個小問題，來自我們知道的 DDH 假設 $ g^{xy} $ 是隨機的。
事實上，這不是真的。DDH 假設說的是我們無法區分 $ g^{xy} $ 從 $ g^z $ ; 但是，它並沒有說我們無法將它們與隨機字元串區分開來。
確實，我們可以；如果順序 $ g $ 沒有小因數，那麼 $ g $ 必須是二次餘數（即，必須存在一個值 $ h $ 和 $ h^2 = g $ ; 這很容易測試）；因此 $ g^{xy} $ 也必須是二次餘數。但是，隨機字元串不是機率為 0.5 的二次餘數，因此可以用作區分符。
而如果 $ g $ 不是二次餘數，那麼 DDH 假設和隨機保持的不可區分性都不是，假設攻擊者可以看到 $ g^x $ 和 $ g^y $ ; 那是因為 $ g^{xy} $ 是二次剩餘當且僅當 $ g^x $ , $ g^y $ 是二次殘差（因此攻擊者可以計算是否 $ g^{xy} $ 是，即使他不知道價值）。
這就是為什麼耶胡達告訴你散列 $ g^{xy} $ 第一的; $ g^{xy} $ 可與隨機字元串區分開來（儘管不一定是由於任何單個位的偏差）， $ \text{hash}(g^{xy}) $ 不是。