IT用語集 › セキュリティ › ラッセル・インパリアッゾ(Russell Impagliazzo)

ラッセル・インパリアッゾ(Russell Impagliazzo)

セキュリティ Svenska → 更新: 2026-10-24

あらゆる可能な宇宙を、そこでどれだけ暗号が作れるかによって五つに分類した、UCサンディエゴの計算複雑性理論家。

インパリアッゾは『A Personal View of Average-Case Complexity』(1995年)で五つの世界を描いた。P = NPが成り立つAlgorithmica、困難な問題はあるが役に立たないHeuristicaとPessiland、一方向性関数はあるが公開鍵暗号はないMinicrypt、そして私たちが住んでいると信じられているCryptomaniaである。どれが現実なのかは、まだ誰にも分かっていない。

この比喩の背後には硬い成果がある。1989年にはルビーとともに暗号には一方向性関数が必要であることを、ルディッチとは一方向性関数から鍵交換をブラックボックス的に導けないことを、そしてホーシュタッド、レヴィン、ルビーとの共著(HILL)では、任意の一方向性関数から擬似乱数生成器が得られることを示した。

← 用語集に戻る