ジェネリックグループモデル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/01 06:42 UTC 版)
ナビゲーションに移動 検索に移動ジェネリックグループモデル(generic group model)[1] [2]は、暗号理論において用いられる群 (数学)を理想化したモデルである。一般に用いられる有限体や楕円曲線グループでは群の各要素は効率的に表現されるが、このモデルにおいては、群の各要素はランダムに選ばれた表現方法によって表現される。
このモデルでは、群演算を実行するオラクルが存在する。このオラクルへ二つの群要素の表現を入力すると、それらを演算した結果の要素の表現が出力される。群がペアリング演算を許す場合、この演算を実行する別のオラクルもモデル化される。
ジェネリックグループモデルの主な利用目的は、計算量的仮定の解析である。このモデルでは、「ある計算量的仮定を破る最も速いジェネリックアルゴリズムは何か？」という問いに答えることができる。ここで、ジェネリックアルゴリズムとは、群演算のみを使い、群の表現方法は考慮しないアルゴリズムである。離散対数問題に対する上記の問いは、ジェネリックグループモデルを用いてVictorShoupによって答えが与えられた。[1]ジェネリックグループモデルの他の結果として、例えば[3]がある。このモデルは、環などの他の代数的構造に拡張することもできる。 [4]
ジェネリックグループモデルには、ランダムオラクルモデルと同様の問題点を抱えている。特に、デントは[5]「ジェネリックグループモデルにおいては証明可能安全が保証されるが、効率よく計算可能な表現方法を一つ固定すると、容易に攻撃が成功してしまう暗号方式が存在する」ことを、カネッティ [6]と同様の議論で示している。
- ^ a b Victor Shoup (1997). “Lower bounds for discrete logarithms and related problems”. Lecture Notes in Computer Science. 1233. Advances in Cryptology – Eurocrypt ’97. Springer-Verlag. pp. 256–266 2010年4月9日閲覧。
- ^ Ueli Maurer (2005). “Abstract models of computation in cryptography”. Lecture Notes in Computer Science. 2796. 10th IMA Conference On Cryptography and Coding. Springer-Verlag. pp. 1–12 2007年11月1日閲覧。
- ^ Ueli M. Maurer, Stefan Wolf: Lower Bounds on Generic Algorithms in Groups. EUROCRYPT 1998: 72-84
- ^ Divesh Aggarwal, Ueli Maurer: Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009:36-53
- ^ Alexander W. Dent: Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model. ASIACRYPT 2002: 100-109
- ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).
- ジェネリックグループモデルのページへのリンク
