暗号論的擬似乱数生成器
通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと(統計的無作為性の試験に合格すること)、第二に、激しい攻撃にも耐えること(初期状態や途中の状態が攻撃者に明らかになっても破られないこと)である。
全てのCSPRNGは "next-bit test" に合格する。next-bit test とは、乱数列の最初の k ビットを与えられたとき、k+1 番目のビットの値を多項式時間で2分の1をこえる確率で予測するアルゴリズムが存在しないことを確認する試験である。アンドリュー・チーチー・ヤオは1982年、next-bit test に合格した生成器は、無作為性に関する他の多項式時間統計試験にも合格することを証明した。
全てのCSPRNGは "state compromise extensions" に耐える。その状態の一部または全部が明らかになっても(あるいは正しく推測されても)、明らかにされた状態より以前に生成された乱数列は再現できない。
さらに、実行中にエントロピーの入力がある場合、その入力を知っていてもCSPRNGの将来の状態を予測できない。
例: 円周率の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。これはnext-bit testを満足するが暗号論的に安全ではない。なぜなら、アルゴリズムの状態にあたる「円周率のどの部分が現在使われているか」を攻撃者が突き止めた場合、その攻撃者は先行するビットをすべて計算できるからである。
多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、リバースエンジニアリングには耐性がない。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。
CSPRNGは、このような暗号解読に対抗するものとして設計される。
Santha と Vazirani は、無作為性の弱いビット列を複数組み合わせることで高品質な擬似乱数列を生成できることを証明した。それ以前にジョン・フォン・ノイマンはビット列からバイアスの大部分を除去できる簡単なアルゴリズムがあることを証明し、Santha-Vazirani の設計に基づいたCSPRNGでフォン・ノイマンのアルゴリズムを入力ビット列に適用する必要がある。これを entropy extraction(エントロピー抽出)と呼び、研究が盛んな領域である。