About: ジェネリックグループモデル

ジェネリックグループモデル(generic group model) は、暗号理論において用いられる群 (数学)を理想化したモデルである。一般に用いられる有限体や楕円曲線グループでは群の各要素は効率的に表現されるが、このモデルにおいては、群の各要素はランダムに選ばれた表現方法によって表現される。 このモデルでは、群演算を実行するオラクルが存在する。このオラクルへ二つの群要素の表現を入力すると、それらを演算した結果の要素の表現が出力される。群がペアリング演算を許す場合、この演算を実行する別のオラクルもモデル化される。 ジェネリックグループモデルの主な利用目的は、計算量的仮定の解析である。このモデルでは、「ある計算量的仮定を破る最も速いジェネリックアルゴリズムは何か？」という問いに答えることができる。ここで、ジェネリックアルゴリズムとは、群演算のみを使い、群の表現方法は考慮しないアルゴリズムである。離散対数問題に対する上記の問いは、ジェネリックグループモデルを用いてVictorShoupによって答えが与えられた。ジェネリックグループモデルの他の結果として、例えばがある。このモデルは、環などの他の代数的構造に拡張することもできる。