Dec. 2023No.101
Interview
安全な暗号の存在を証明する
現代の情報通信社会において、キーとなる暗号技術。現在使われている暗号が本当に安全と言えるのかを数学的に証明するのが、平原 秀一 准教授の研究目標だ。世界の数学者と肩を並べ、難題に取り組むその研究の展望を聞いた。
平原 秀一HIRAHARA, Shuichi
国立情報学研究所
情報学プリンシプル研究系 准教授
暗号化技術は本当に安全なのかを問う
──計算量理論とは、どのような研究なのでしょうか。
計算量理論は、さまざまな計算問題を解くのに必要な計算量（計算時間や必要なメモリの量など）を証明する理論です。その中で私が進めているのは、ある計算問題を解くことが困難であることを最終的に証明する研究で、暗号理論に深く関わっています。
私たちが日頃から利用しているネットショッピングや店頭でのクレジットカード支払いなどは、公開鍵暗号方式という暗号化の技術によって決済情報が守られています。クレジットカードの番号を入力したり、銀行にパスワードを送ったりする際に、途中で盗聴されても解読できないように暗号化されているのです。ところが、この公開鍵暗号方式が本当に安全なのかどうかは、いまだに証明されていません。例えば、公開鍵暗号方式の一つであるRSA暗号は、素因数分解の計算が解読困難であるという前提に基づいています。この素因数分解の計算が、本当に解読困難であることを証明するのが私の研究です。
代表的な問題に「P≠NP予想」というものがあります。これは、2000年にアメリカのクレイ数学研究所が100万ドルの賞金を懸けた「ミレニアム懸賞問題」という七つの未解決問題の中の一つです。「P≠NP予想」とは、解の正しさは検証できるが計算するのが難しい問題の存在を証明することであり、これが証明できなければ暗号の安全性が成り立たないという重要な課題です。
──具体的には、どのようにして公開鍵暗号方式の安全性を確立するのですか。
実は「P≠NP予想」を解決するだけでは公開鍵暗号方式の安全性を担保するには不十分で、平均時計算量の観点から計算困難性を解析する必要があります。平均時計算量とはアルゴリズムの計算時間の平均のことで、平均時計算量の観点から見た「P≠NP予想」 は「DistNP ⊈ AvgP予想」と呼ばれます。公開鍵暗号方式の安全性を確立するには、「P≠NP予想」を解決した上で「DistNP ⊈ AvgP予想」を解決する必要があるのです。
この他にも、公開鍵暗号方式の安全性を確立するにはいくつものステップが必要になるのですが、そのステップを数学者のRussellImpagliazzo氏 は1995年 に「Algorithmica」「Heuristica」「Pessiland」「Minicrypt」「Cryptomania」という五つの可能世界に分類して示しました。例えば「Algorithmica」 は、P=NPであった時の我々の世界を表しています。この世界では、さまざまな最適化問題が高速に解けますが、同時にどのような公開鍵暗号方式でも容易に破られてしまいます。それに対して、「Cryptomania」は安全な公開鍵暗号が存在する世界で、多くの研究者は我々の世界は「Cryptomania」であると予想しています。一つずつ重要な未解決問題を解決し、「我々の世界はCryptomaniaである」という予想を証明することが、数学的に裏付けされた絶対的に安全な暗号の存在の証明になるのです。
理論計算機科学における世界最高峰の賞に選出
──2022年に選出された"Complexity result of the year"について教えてください。
部分関数版回路最小化問題のNP完全性（NPの中で最も難しい未解決問題であること）を解決したことが評価され、いただいた賞です。この研究成果は、理論計算機科学における世界最高峰の国際会議FOCSにも採択されました。
──その成果が、公開鍵暗号の安全性を確立することにつながるのですね。
とはいえ、実際にHeuristicaを除外するには、どのように証明できるか分からないので、どのくらい時間がかかるのか想像がつきません。私が生きている間に、「Heuristicaの除外」をなんとかなし得たいですね。
数百年後の未来に貢献する
──いつ頃から、このような超難題に挑もうと考えるようになったのでしょうか。
私が計算量理論に初めて触れたのは、大学3年生の時です。その頃に「ミレニアム懸賞問題」を知り、なぜこんなに難しい問題があるのかが気になり、計算量理論に興味を持ちました。元々、理論的に考えることが好きなので、そういった難しい問題に挑戦したいと思うようになりました。
その後、回路最小化問題に修士2年の時から取り組み、世界で初めて非ブラックボックス帰着手法を開発して、「回路最小化問題のNP完全性が解決できれば、NPの最悪時•平均時計算量が同値である(Heuristicaが除外できる）」ということを証明しました。それによって、日本人で初めて MachteyAward（FOCS2018、最優秀学生論文賞）を受賞しています。RSA暗号は当面破られないと思われていますが、もし世界のどこかで密かに「P=NP」を解決した人がいれば、世界の安全は崩れてしまいます。数百年後の未来に貢献するために、この研究は必要なのです。
──研究を進めていく上で、国立情報学研究所（NII）の環境はいかがでしょうか。
日常的に研究のことばかり考えている自分にとって、腰を据えた研究ができるだけの十分な研究時間が与えられるNIIの環境はとても適していると感じています。これからも、未解決問題に取り組み、少しでも未来に貢献する研究に励みたいと思います。