ElGamal 加密中的資訊洩漏與基組中的消息
假設一個有限交換基群 $ \mathbb B $ ， 一些 $ g $ 在 $ \mathbb B $ ， 和 $ \mathbb{G} = \langle g\rangle $ 那個子群 $ g $ 生成，可選擇 $ \mathbb B $ 和 $ g $ 這樣 ElGamal 加密對於隨機消息是安全的 $ \mathbb G $ （語義上/在 CPA 下）。
如果我們使用隨機消息，ElGamal 加密仍然允許解密 $ \mathbb B $ 而不是在 $ \mathbb G $ . 如果我們這樣做，會洩露多少關於消息的資訊？如果需要獲得結果，請限制為 $ \mathbb B=\mathbb Z^*_p $ ，也許與 $ p $ 一個奇數素數，和/或 $ \mathbb G $ 素數的。
符號：順序 $ \mathbb G $ 由產生 $ g\in \mathbb B $ （以乘法表示）是 $ q $ ; 私鑰 $ x $ 是均勻隨機的 $ 0<x<q $ ; 公鑰是 $ h=g^x $ . 加密 $ m $ 消息空間中的隨機（ $ \mathbb G $ 對於 ElGamal 加密的標准定義， $ \mathbb B $ 在問題中）生成一次性 $ y $ 均勻隨機 $ 0<y<q $ , 併計算 $ c_1=g^y $ , $ s=h^y=g^{x,y} $ , $ c_2=m,s $ . 密文是 $ (c_1,c_2) $ . 解密重新計算 $ m $ 作為 $ c_1^{q-x},c_2 $ .
眾所周知，如果 $ \mathbb B=\mathbb Z^*_p $ 和 $ p $ 一個大素數和 $ \mathbb G $ 素數的 $ (p-1)/2 $ ，存在一位資訊洩露：我們可以從密文中判斷明文是否為二次餘數；但據我們所知，沒有別的了。我不確定其他許多情況（ $ \mathbb G $ 較小的質數順序，或不是質數順序；其他基組）。
我在回答這個問題時出現了這個問題的動機。
讓一個素數 $ p = 2qs + 1 $ . 考慮子組 $ \mathbb{G} = \langle g \rangle $ 有秩序的 $ q $ . 公鑰是 $ h = g^x \bmod p $ 而私鑰是 $ x \in \mathbb{Z}_q $ . 的加密 $ m $ 是（誰）給的 $ (c_1, c_2) $ 和 $ c_1 = g^r \bmod p $ 和 $ c_2 = m \cdot h^r \bmod p $ 對於隨機整數 $ r \gets \mathbb{Z}_q $ . 語義安全要求該消息 $ m $ 屬於 $ \mathbb{G} $ .
讓 $ z $ 成為 $ \mathbb{F}p^* $ . 所以我們可以寫 $ m = z^M \bmod p $ 對於一些 $ M \in \mathbb{Z}{p-1} $ .
- 提高 $ c_2 $ 的力量 $ qs $ 產量$$ {c_2}^{qs} \equiv z^{Mqs \bmod (p-1)} \equiv (z^{qs})^{M\bmod 2} \equiv (-1)^{M\bmod 2} \pmod p $$ 的價值 $ (M \bmod 2) $ 表示是否消息 $ m $ 是一個正方形 $ \mathbb{F}_p^* $ .
- 提高 $ c_2 $ 的力量 $ 2q $ 產量$$ {c_2}^{2q} \equiv z^{M2q \bmod (p-1)} \equiv (z^{2q})^{M\bmod s} \pmod p $$ 如果 $ s $ 小或平滑，攻擊者可以恢復 $ (M \bmod s) $ 作為離散對數 $ \mathbb{F}_p^* $ 的 $ {c_2}^{2q} $ 關於基地 $ z^{2q} $ .
設一個密碼函式 $ H \colon \mathbb{G} \to \mathbb{F}p^* $ 被視為隨機預言機。語義安全可以通過消息空間來滿足 $ \mathbb{F}{p}^* $ 通過將密文定義為對 $ (c_1, c_2) $ 和 $ c_1 = g^r \bmod p $ 和 $ c_2 = [m \cdot H(h^r \bmod p)] \bmod p $ 對於隨機整數 $ r \gets \mathbb{Z}_q $ . 解密 $ (c_1, c_2) $ 獲得為 $ m = [c_2 /H({c_1}^x \bmod p)] \bmod p $ .
在沒有隨機預言的情況下獲得語義安全的另一種選擇是採取 $ s = 1 $ ( $ p = 2q+1 $ 是一個安全的素數）。有效消息集僅限於 $ \mathcal{M} = {1, \dotsc, (p-1)/2} $ . 消息的加密 $ m \in \mathcal{M} $ 由對給出 $ (c_1, c_2) $ 和 $ c_1 = g^r \bmod p $ 和 $ c_2 = m^2 \cdot h^r \bmod p $ 對於隨機整數 $ r \gets \mathbb{Z}_q $ . 解密 $ (c_1, c_2) $ 分兩步獲得 $ m^2 = c_2 /{c_1}^x \bmod p $ 接著 $ m $ 作為平方根（模 $ p $ ） 的 $ m^2 $ 在集合中 $ \mathcal{M} $ . 請注意，如果 $ m \in \mathcal{M} $ 然後 $ -m \bmod p = p-m \notin \mathcal{M} $ .
一般來說，如果你使用 $ \mathbb{Z}p^* $ 和 $ p = q\cdot \prod{i=1}^t p_i + 1 $ , 其中 $ p_i $ 是不同的小素數，那麼你將有 $ O(t) $ 位洩漏。因此，直覺地說，如果我們這樣做，很多資訊可能會洩露：最多 $ O(\log p) $ 使用這種方法，因此可以達到消息所有位的恆定比例。正如另一個答案中所指出的那樣，一般來說，這相對容易避免。
編輯：正如 Vadym Fedyukovych 在評論中指出的那樣，對洩漏的更精確評估 $ p $ 上面的形式，包括低階項，是 $ O(t\log\log p) $ .