ジェネリックグループモデルでは、もう1つの離散対数問題は難しいですか？
ジェネリックグループモデル（GGM）では、（既知の）次数の具体的な巡回群 $n$は理想的なバージョンに置き換えられます。グループ要素のランダムエンコーディングが選択され、攻撃者は入力グループ要素（ジェネレータ/公開鍵/ ...など）のエンコードされた形式と、適用するオラクルにのみアクセスできます。それらのグループ操作。エンコーディングは一意であるため、グループ要素が等しいかどうかをテストできます。これは、ハッシュではなく、グループのランダムオラクルモデルの類似物と見なすことができます。
GGMでは離散対数の問題が難しいことはよく知られています。Shoupは、一般的なアルゴリズムには$\Omega(\sqrt{p})$ グループ操作、ここで $p$ の最大の素因数です $n$。
私の質問は、もう1つの離散対数問題（OMDL）がGGMでも難しいかどうかです。OMDLを破るために、敵が与えられます$k+1$ ランダムなグループ要素は、作ることができます $k$ DLオラクルにクエリを実行し、すべての離散対数を見つけることに成功する必要があります $k+1$ 入力。
回答
はい、これはCoretti et al [CDG]の最近の研究で示されました。大まかに言えば、下限は、せいぜい敵を作ると述べています$T$ GGMオラクルへのクエリは最大で確率で成功します $T^2/N$、 どこ $N$グループのサイズです。実際、彼らは、敵がGGMで任意の事前計算を許可されているより強力なモデルを検討しています。より正確なステートメントについては§5を、結果の要約については表2を参照してください。
[CDG]：Coretti、Dodis、Guo、ランダム置換、理想暗号、ジェネリックグループモデルの不均一な境界、Crypto'18