Scribble at 2025-02-13 16:34:52 Last modified: unmodified

Russell Impagliazzo というカリフォルニア大学の研究者が提唱した、暗号論的な５つの可能世界（logic の話ではないから、「想像の世界」と言った方がいいが）という話題は、もちろん情報セキュリティに関わる実務家や理論家にとっての常識的な信念として共有しておいてもいいコンセプトだろうと思う。ただ、そのためには「P=NP問題」という話題を共有する必要もあるので、やはり計算論の概念を習得することは重要だ。残念ながら、日本ではコンピュータ・サイエンス学科を出ていない人々に、この手の概念は殆ど知られていないし、知る必要があるとも考えられていないので、IT ベンチャーとは言ってもアメリカや中国やインドの学生と日本の学生とでは、背景知識や常識的な信念にズレや違いがある。

イムパグリアツォの掲げた五つの世界で、まず「アルゴリズミカ」と呼ばれる世界は、暗号化も復号化も特定のアルゴリズムが存在して多項式時間内に処理が終わるし処理の正しさも確認できるので、原理的には暗号化に意味がない。そもそも僕らが利用しているアルゴリズムは、多項式時間内で逆演算を終えるのが困難であるという特性によって暗号化としての安全性が保証されているから、どんな演算（暗号化）をしても逆演算（復号化）が多項式時間内で完了してしまうのであれば、その時間をどんどん短くできるのは単なるマシンのスペックという問題でしかなくなる。

逆に、「ペシランド」もしくはイムパグリアツォにとっての地獄と呼ばれる世界では、暗号化が容易でも復号化が容易ではない一方向性関数が存在しないにもかかわらず NP 問題もたいてい難しいので、これは要するにどんな暗号化のアルゴリズムも容易には信用できないということである。これも、どんな暗号化アルゴリズムも容易に復号されるのと同じくらい困った世界であり、そもそもアルゴリズムと呼べるかどうかすら怪しい手続きに頼るしかない。また、それが正しいかどうかを確かめる演算すら多項式時間内に終わらない。

このように、「計算できる」ということの有効性がどんな指標で測られていて、それが暗号化や情報の保護にとって有利なのか不利なのかも異なるという原理的な理解がなければ、情報セキュリティの研究者どころか実務家としても公平で的確なスタンスを確立したり維持することは難しい。