暗号論的擬似乱数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/09 18:40 UTC 版)
詳細は「暗号論的擬似乱数生成器」を参照 一般の擬似乱数は、その方式と過去の出力が既知であれば、未来の出力を予測可能であるため、暗号の用途には不適（暗号学的に安全ではないと言う）である。 暗号理論では擬似乱数（生成器）に明確な定義がある。すなわち、多項式時間の計算機が乱数列と識別不能な列を出力する機器のことを、暗号論的擬似乱数生成器と呼び、この列に含まれる数を暗号論的擬似乱数という。いかなる数列であれば乱数列であるか、議論のあるところではあるが、一様分布であることと過去の数から次の数が予測不能であることは同値であることが示されている（Yao）。そこで過去の数から次の数が予測不能であるかで、暗号論的擬似乱数か否かを区別する。 暗号理論では擬似乱数に厳密な定義が与えられている。Σ = {0,1}とする。自然数 k に対し、Σk 上の一様分布を Uk と表す。確率変数の族 {Xk}k∈N が、一様分布の族 {Uk}k∈N と計算量的識別不能な時、族 {Xk}k∈N は暗号論的擬似乱数であるという。 次に暗号論的擬似乱数生成器の厳密な定義をする。l(k) を l(k) > k を満たす多項式とする。G を多項式時間アルゴリズムで、G に k ビットのビット列を入力をすると l(k) ビットの出力を返すものとする。すると G(Uk) は Σl(k) 上の確率分布である。確率分布の族 {G(Uk)}k∈N が暗号論的擬似乱数である時、多項式時間アルゴリズム G を暗号論的擬似乱数生成器という。 一方向性関数が存在すれば暗号論的擬似乱数生成器が存在する事が知られている。 実際の生成法としては、一般の擬似乱数列を暗号学的ハッシュ関数に通す、という、簡単な構成法がある。
※この「暗号論的擬似乱数」の解説は、「擬似乱数」の解説の一部です。
「暗号論的擬似乱数」を含む「擬似乱数」の記事については、「擬似乱数」の概要を参照ください。
- 暗号論的擬似乱数のページへのリンク
