一方向性とは, 一つの関数の計算に比べてその逆関数の計算が難し
い性質である. ここでは一方向性の度合を, その関数を計算する回
路の複雑度と逆関数を計算する回路の複雑度の比率で計る. この論
文では, 始めに三角行列で記述され得る線形置換について, その一
方向性の度合の上限が入力サイズnに対して, 16√nで押えられるこ
とを証明し, この逆関数が線形置換の中でほぼ最大の複雑さをもつ
場合, 一方向性の度合が定数で押えられることを示す. 次に, 三角
行列で記述され得る線形置換と, 線形置換, 非線形置換を一方向性
の度合について比較する. 更に, 三角行列で記述され得る線形置換
において, 一方向性の度合を高める為の条件を考察する.
Back