Hardness-Assumptions
DDH 對這個組很難嗎？
我是 DDH 的新手。閱讀此調查，我注意到 DDH 在許多組中（被認為是）很難，但其中大多數是素數階組（唯一不是順序的循環子組 $ (p-1)(q-1) $ 整數組的模 $ N = pq $ ）。我的問題是關於這個特定複合階組中 DDH 的硬度：
讓 $ q $ 是一個素數，使得 $ p = 4q+1 $ 是一個素數。DDH 在 order 的子組中難嗎 $ 2q $ 的 $ \Bbb Z_{p}^\ast $ ?
關於這個組的注意事項：我的代數背景相當基礎，我什至不知道這個組是否保證存在，如果存在，是否保證是循環的。
DDH 在 order 的子組中難嗎 $ 2q $ 的 $ \mathbb{Z}_p^* $
不它不是。
如果定義函式 $ F(x) = x^{q} \bmod p $ ，那麼對於任何 $ x $ 是\n訂單組 $ 2q $ ， 我們有 $ F(x)= 1 $ 如果 $ x $ 是正確子群的成員 $ q $ ， 和 $ -1 $ 如果不是。而且，恰好有一半的元素將在該子組中。
你總會有一個偶數（0或2） $ F(g^a) $ , $ F(g^b) $ , $ F(g^{ab}) $ 為-1；如果你發現奇數個 $ F(g^a) $ , $ F(g^b) $ , $ F(g^c) $ 是-1，那麼你已經確定這不是一個DH三元組。
此邏輯適用於任何具有小因素訂單的組。