暗号学的擬似乱数

素因数分解の困難性など、効率的に解くアルゴリズムが存在しないだろうと信じられている問題がありますが、そういった問題の困難性の仮定に基づいて擬似乱数生成器を構成することができます。それらの擬似乱数生成器は困難性の仮定が真であれば、現実的な時間ではそれまでの全ての出力を観測したところで次の値を予測できない (予測が当たる確率が1/2から無視可能な程度以上離れていない)。こういった擬似乱数生成器を暗号学的擬似乱数生成器と言います。具体的なアルゴリズムとしては、Blum-Blum-Shubなどがあります。

また、ハッシュ関数など一方向性関数であると信じられている関数を利用することで、予測困難性を確保する擬似乱数生成器もあります。ただ、数論の仮定を利用した上記の暗号学的擬似乱数生成器とは違い、証明可能な安全性は持っていません。あくまで、経験的に一方向性があり、予測困難と信じられていることを利用しています。