フェイステル変換を用いた近似的k-対ランダム置換族の構成

概要

論文の詳細を見る
一般にk-対ランダム置換族は,偽造不可能な署名方式の設計や確率的アルゴリズムの決定性アルゴリズムヘの変換等の応用を待つことが知られている.しかし,実用的な状況ではε-近似的k-対ランダム置換族で代用可能な場合が想定され,そのような条件緩和によってより効率的な置換族の実現が期待される.任意の整数n>0に対してS_nを集合{0,1,...,n-1}上の置換全体とする.本論文では共通鍵暗号方式DES (Data Encryption Standard)の設計において本質的な役割を果たすフェイステル変換を繰り返し用いて置換族を構成し,任意のn=p^<2h>(p: 素数;h>O)に対してk = O(log n)であるならば|F|=(n^<k^<k>>/ε^k)^<3+o>(1)を満たすε-近似的k-対ランダム置換族F⊆S_nが構成可能であることを示す(これはε-近似的κ-対ランダム置換族F⊆S_nの非自明な最初の構成法である).さらに,本論文で構成された置換族がO(log n)-領域要素別法本可能であることを示す.
2004-04-15