泛型組模型中的多離散對數問題難嗎？
在泛型群模型（GGM）中，一個（已知）階的具體循環群 $ n $ 替換為理想化版本：選擇組元素的隨機編碼，攻擊者只能訪問任何輸入組元素的編碼形式（例如生成器/公鑰/…），並應用預言機對它們進行分組操作。編碼是唯一的，因此可以測試組元素是否相等。它可以看作是組而不是散列的隨機 Oracle 模型的類似物。
眾所周知，離散對數問題在 GGM 中很難解決：Shoup表明任何通用算法都需要 $ \Omega(\sqrt{p}) $ 組操作，其中 $ p $ 是最大的質因數 $ n $ .
我的問題是，在 GGM 中，另一個離散對數問題 (OMDL) 是否也很困難。為了打破 OMDL，給出了一個對手 $ k+1 $ 隨機群元素，可以使 $ k $ 對 DL oracle 的查詢，然後必須成功找到所有的離散對數 $ k+1 $ 輸入。
Bauer 等人最近的工作。
$$ BFP $$聲稱先前答案中的證明是有缺陷的（並且 Coretti 等人證實了這一點）。然而，鮑爾等人。在 GGM 中證明 OMDL 的硬度。他們表明，對手以素數順序的通用組解決 OMDL（無需預先計算）的機率 $ N $ 並且最多製作 $ T $ oracle 查詢最多 $ T^2/(N - T^2) + 1/N $ . $$ BFP $$: Bauer, Fuchsbauer, Plouviez,泛群模型中的再離散對數假設
是的，這在 Coretti 等人最近的一項工作中得到了展示
$$ CDG $$. 粗略地說，下界表示一個對手最多 $ T $ 對 GGM 預言機的查詢最多以機率成功 $ T^2/N $ ， 在哪裡 $ N $ 是組的大小。他們實際上考慮了一個更強大的模型，其中允許對手在 GGM 中進行任意預計算。有關更精確的陳述，請參見第 5 節，有關其結果的摘要，請參見表 2。 $$ CDG $$: Coretti、Dodis 和 Guo，隨機排列、理想密碼和泛型組模型中的非均勻界限，Crypto'18