為什麼DDH不難結束從∗p從p∗mathbb{Z}^*_p?
為什麼 Diffie-Hellman 密鑰交換不難結束 $ \mathbb{Z}^{*}_p $ ?
如果 DDH 在一個組中很難 $ G $ 帶發電機 $ g $ ，那麼很難決定給定 $ (g,g^a,g^b,g^c) $ 無論 $ ab\equiv c\pmod{ord(G)} $ .
如果你認為 $ G $ 群組 $ Z_p^* $ 有秩序的 $ p-1 $ 和 $ p $ 是素數，那麼你將擁有 $ (p-1)/2 $ 元素是二次餘數 ( $ QR $ ) 另一半是非二次殘差 ( $ QNR $ ).
現在，我們知道 $ QR\cdot QR = QR $ , $ QNR\cdot QNR = NQR $ 和 $ QR \cdot QNR = QR $ , 其中 $ \cdot $ 運算符有效果 $ g^a \cdot g^b = g^{ab} $ . 這些身份微不足道，因為 QR 的形式是 $ g^{2k} $ 在哪裡 $ k\in \mathbb{Z} $ ， 所以 $ g^{2k} \cdot g^b = g^{2(kb)} $ 這是一個二維碼。
所以給定一個元組 $ (g,g^a,g^b,g^c) $ ，我們可以檢查 $ g^a $ , $ g^b $ 和 $ g^c $ 他們是否 $ QR $ 或者 $ QNR $ ，即計算它們的勒讓德符號。
請注意，如果這是一個有效的 DDH 元組，那麼您可以將其寫為 $ (g^a,g^b,g^{ab}) $ 如果你遇到這種情況 $ (QR,QR,QNR) $ , $ (QNR,QR,NQR) $ , $ (QR,QNR,NQR) $ 或者 $ (QNR,QNR,QR) $ 那麼它不可能是這樣的 $ ab\equiv c\pmod{p} $ ，這為您提供了 DDH 的區分符。
更正式地說，DDH 問題只有在 $ x, y, z \in G $ 我們有
$$ |\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)|\leq \text{negl}(l) $$
一個對手 $ \mathcal{A} $ 可以採用以下策略：檢查是否為提供的 $ g^a, g^b, g^c $ 上述 QR/NQR 身份保持不變。如果他們這樣做，那麼輸出 $ 1 $ . 否則，輸出 $ 0 $ .
注意 $ P(g^x = QR) = 1/2 $ 對於隨機 $ x\in G $ . 因此，根據上述恆等式， $ g^{ab} $ 是 QR 是 $ 3/4 $ （這也是任何一個的機率 $ g^a $ 或者 $ g^b $ 是二維碼）。那麼上面的機率就變成了：
$$ \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1) = 1 $$ $$ \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1) = \frac{3}{4}\times\frac{1}{2} + \frac{1}{4}\times\frac{1}{2} = \frac{1}{2} $$ 作為一個有效的 DH 元組將始終遵循 QR/NQR 身份。同時，如果 $ z \neq xy $ , 然後對手輸出 $ 1 $ 如果碰巧元組與身份一致（所以機率是 [prob that either $ g^a $ 或者 $ g^b $ 是 QR 和 $ g^c $ 是 QR] 或
$$ the same thing with NQR $$). 因此， $ |\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)| = \frac{1}{2} \nleq \text{negl}(l) $ 所以問題並不難，正式。
如果你選擇 $ p $ 成為安全素數，即，形式為 $ p=2q+1 $ 和 $ q $ 但是，也是素數，並且您以素數順序工作 $ q $ 子群，DDH 很難（然後你在二次殘差的子群中工作，你將不再有上述方法來建構區分器）！
在應用 Diffie-Hellman 問題時常用的代數群是Schnorr 群。這些是 $ \mathbb{Z}_p^* $ 並有形式 $ G_S = {h^r \text{ mod } p\ |\ h \in \mathbb{Z}_p^*} $ 在哪裡 $ p=rq + 1 $ 和 $ p,q $ 是素數。那麼組的順序是 $ q = (p-1)/r $ .
請注意，在這種情況下 $ p,q $ 一定是奇怪的（除了微不足道的情況 $ q=2 $ ）， 意思就是 $ r=2s $ 對於一些 $ s\in \mathbb{N} $ （IE $ r $ 甚至）。這意味著所有元素都是二次殘差 $ \mathbb{Z}_p^* $ 因此上述區分符將不適用。
此外，可以針對三次、四次等殘差建構對 DDH 的類似攻擊。形式上，您可以為任何 $ k $ 給定的殘差 $ k $ 劃分組順序。團體順序為 $ \mathbb{Z}_p^* $ 在哪裡 $ p=rq+1 $ ，如上所述，是 $ p-1 = rq $ . 因此，我們需要檢查 $ r $ th 殘差（作為子組的所有元素不提供任何區分能力 $ G_S $ 是 $ r $ th 殘差）和 $ q $ 殘差（沒有用，因為它只包括 $ 1 $ 由於 $ q $ 是素數）。
選擇 Schnorr 組，使得 $ p\gg q $ ， 導致 $ r $ 很大並且有很多主要因素，使任何形式的 $ k $ 由於上述原因，殘餘攻擊的成功機會微乎其微。儘管 $ k $ th 殘餘攻擊大 $ k $ s 迅速停止給予任何明顯的歧視權力。
但是 DDH 並不是 Diffie-Hellman 密鑰交換的硬度假設，而是依賴於 CDHP，即，給定 $ (g,g^a,g^b) $ 計算 $ g^{ab} $ , 這很難 $ Z_p^* $ 為適當的選擇 $ p $ . 這是竊聽者在攔截時面臨的問題 $ g^a $ 和 $ g^b $ 計算公共密鑰 $ g^{ab} $ . 請注意，針對 Diffie-Hellman 密鑰交換的竊聽者希望永遠不會看到 DDH 元組 $ (g^a,g^b,g^{ab}) $ 否則這將意味著各方將發送交換的密鑰 $ g^{ab} $ 通過電線清除，這不是一個好主意；）