■
(暗号学的)疑似乱数生成の話.
証明の手法としては,
- 識別機が存在すると, 一方向性が破れることを言う.
- HSSとかGRはこの一種か.
- hard-core predicate (function)を作る
- Blum-Blum-ShubとかGoldreich-Levinとか. List-decodingと関係してくる. フーリエ変換+List-decodingになる(らしい).
- 一方向性を言っておく. のち, 識別機が存在すると, 一方向性から言えるhard-core predicateが破れることを示す.
- Impagliazzo-Naor
くらいか.
2, 3がダメだったので, 1に戻してみる.