研究 / Research

真に安全な暗号とは？

現在の社会は情報通信技術の上に成り立っています。その安全性を支えているのが素因数分解の計算困難性に基づくRSA暗号です。しかし、RSA暗号は理論的に解読不可能と証明されておらず、コンピュータの処理能力が向上したり、革新的なアルゴリズムが開発されたりすると解読される可能性があります。そこで、数学的に絶対に解読不可能な暗号の開発が求められています。

暗号が解読不可能であるためには、100万ドルがかけられたミレニアム懸賞問題の一つである「P≠NP予想」を肯定的に解決しなければなりませんが、未だに証明されていません。Pは効率的に計算できる問題全体、NPは効率的に解の正しさを検証できる問題全体で、もしP=NPだとすると全ての暗号が破られてしまいます。さらに、解読できない暗号を構成するためにはP≠NPを示すだけでは不十分であることが知られており、例えば「NPの最悪時・平均時計算量が同値」であることを示す必要があります。

より詳細に述べると、PやNPといった問題クラスは、アルゴリズムが最も計算時間がかかるような入力での時間（最悪時計算量）を測りますが、一方で、暗号の安全性を議論するためには、「ランダムな秘密鍵を生成したときに、盗聴者がどのくらいの計算時間で暗号を破れるか（平均時計算量）」を議論する必要があります。従って、NPの平均時計算量の意味での難しさも証明する必要があるのです。

日本人初のMachtey Award（最優秀学生論文賞）受賞

P≠NPを証明するには３つのバリア（自然な証明、代数化、相対化）を突破する手法が必要となります。同様に、NPの最悪時・平均時計算量の同値性を示すためにも二つのバリア（相対化、ブラックボックス帰着の限界）を突破する必要があります。

私は、修士2年の時から回路最小化問題（Minimum Circuit Size Problem：MCSP）に取り組んでおり、それが暗号と密接に関わっていると考えました。回路最小化問題に着目することにより、世界で初めて非ブラックボックス帰着手法を開発し、「回路最小化問題のNP完全性が解決できれば、NPの最悪時・平均時計算量が同値である」ということを証明しました。それによって、日本人で初めてMachtey Award（FOCS2018、最優秀学生論文賞）を受賞することができました。

また、回路を制限した場合に回路最小化問題のNP完全性を解決しました。これは、1979年にMasekが深さ2段に制限したMCSPのNP完全性を解決して以来40年間未解決だった、深さ3段以上のNP完全性を証明することができたのです。

数百年後の未来に貢献したい

RSA暗号は当面破られないと思われていますが、密かに（予想に反して）P=NPを解決した人がいれば世界の安全は崩れてしまいます。そこで、絶対的に安全な暗号の確立に向けて研究を進めています。

証明手法が存在しないのでどれくらいの時間がかかるかわかりませんが、生きている間に、絶対に解けない暗号の存在を証明し、数百年後の未来に貢献したいと思います。

リンク

• [NII Today] 安全な暗号の存在を証明する
• [NII SEEDS]より安心・安全な暗号の設計に向け回路最小化問題の計算困難性を解析