擬似ランダム関数から擬似ランダム置換への変換について
スポンサーリンク
概要
- 論文の詳細を見る
DES(Data Encryption Standard)ではS(f)と表される{0,1}^<2n>から{0,1}^<2n>への置換を基本操作として用いている.fを{0,1}^nから{0,1}^nへの関数,⊕をビットごとの排他的論理和を表すとすると,S(f)は,S(f)(L・R)=R・[L⊕f(R)]と定義される.ここで,L,R∈{0,1}^n.また,S(f_2,f_1,f_0)でS(f_2),S(f_1),S(f_0)の合成(composition)を表すものとするものとし,f_0,f_1,f_2を擬似ランダム関数の集合からランダムに選んだとき得られるS(f_2,f_1,f_0)の集合を,{S(f_2,f_1,f_0)}と表すとする.Lubyらは,{S(f_2,f_1,f_0)}は擬似ランダムとなることを証明したが,本論文は,擬似ランダム関数を2種類とした場合について検討し,{S(f_1,f_1,f_0)}や{S(f_1,f_1,f_0)}は擬似ランダムとなるが,{S(f_0,f_1,f_0)}は擬似ランダムとはならないことを導く.
- 社団法人電子情報通信学会の論文
- 1993-08-25
著者
関連論文
- 包除原理による和集合のサイズの評価について
- $\epsilon$-偏りの確率変数と$\epsilon$-依存の確率変数の間の関係について(計算機構とアルゴリズム)
- 包除原理による和集合のサイズの評価について(理論計算機科学とその周辺)
- 二部グラフの拡張性の評価について(計算機科学の基礎理論)
- 循環型シフト回路の埋め込み面積について (形式言語理論とオートマトン理論)
- 1次元-2状態-スコープ3テセレイションオートマトンの完全性について (情報科学の数学的理論)
- 多値論理素子が細分的であるための条件 (情報科学の数学的理論)
- 擬似ランダム関数から擬似ランダム置換への変換について