ニュース / News

ニュースリリース

2024/04/09

﹁メタな視点に基づく平均時計算量の研究﹂で NIIの平原秀一准教授が若手科学者賞を受賞
～令和6年度の文部科学大臣表彰～

　文部科学省が2024年︵令和6年︶4月9日(火)に発表した﹁令和6年度科学技術分野の文部科学大臣表彰﹂において、﹁メタな視点に基づく平均時計算量の研究﹂の業績により、国立情報学研究所︵NエヌIアイIアイ、所長‥黒くろ橋はし禎さだ夫お東京都千代田区︶情報学プリンシプル研究系の平ひら原はら秀しゅ一ういち准教授が、若手科学者賞^︵*1︶を受賞しました。

︻研究の背景︼

　現在、インターネットで広く使われている公開鍵暗号は、情報の暗号化を行う際と復号を行う際に別々の鍵を使う方式で、公開鍵と計算結果であるメッセージの組み合わせから、秘密鍵を計算するのに膨大な時間がかかり困難であることから、安全と言われています。しかし、本当に安全かどうかは未だに証明されていません。その安全性を議論するためには、計算の平均的な難しさを計る﹁平均時計算量﹂がどれくらいなのか解析するのが必要不可欠です。平原准教授は、その平均時計算量を新しい視点から解析するため、﹁計算問題の計算量を問う計算問題︵メタ計算問題︶﹂を考えるという、メタな視点に基づき、証明手法を開発してきました。

︻評価の対象となった研究成果︼

　平均時計算の困難性を示す証明手法として﹁ブラックボックス帰着﹂と呼ばれる手法がありますが、この手法では暗号の安全性を証明するための未解決問題を完全に解決できない﹁ブラックボックス帰着の限界﹂があることがわかっています。平原准教授は、先に述べたメタ計算問題に着目し、ブラックボックス帰着ではない平均時計算困難性を解析するための革新的な証明手法を世界で初めて開発しました。この業績により、長年未解決だった暗号の安全性を証明するための中心的問題の解決への道筋を確立し、2022年には、理論計算機科学のトップ会議であるFOCSに採択されたうえ、その年の最も優れた計算量理論の研究成果に贈られるComplexity result of the yearを日本人で初めて受賞するなど、国際的に非常に高く評価されています。今回、こうした業績が評価され、平原准教授は令和6年度科学技術分野の文部科学大臣表彰の若手科学者賞を受賞しました。

【令和6年度科学技術分野の文部科学大臣表彰　若手科学者賞】
メタな視点に基づく平均時計算量の研究

平原　秀一（ひらはら・しゅういち）

32歳

情報・システム研究機構国立情報学研究所（NII）情報学プリンシプル研究系准教授

︵年齢は2024年4月1日現在︶

業績概要‥

　計算量理論は、計算問題を解くために必要な計算量︵＝計算時間などの計算資源︶を解析する理論である。現在広く使用されている暗号は、計算量理論のP対NP予想や、平均時計算量に一般化されたP対NP予想に基づいており、真に安全かどうかは未解決である。氏は、メタ計算問題︵＝計算問題の計算麓を問う計算問題︶に着目することにより、NPの平均時計算困難性を解析するための革新的な証明手法を開発し、世界で初めて﹁ブラックボックス帰着の限界﹂を突破することに成功した。さらに、計算量理論の根源的定理であるCook-Levin の定理に遡る約50年来の未解決問題を解決した。本研究成果は、我々の日常生活で通信の秘密を守っている暗号技術が本当に安全かどうかを決定し、真に安全な情報通信社会を確立することに資すると期待される。

主要論文‥

●﹁NP-Hardness of Learning Programs and Partial MCSP﹂Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS)、p968~979、2022年発表 ●﹁Non-Black-Box Worst-Case to Average-Case Reductions within NP﹂Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) 、p247~258、2018年発表

平原秀一准教授のコメント‥

　このような名誉ある賞を頂き大変光栄に存じます。計算量理論には多くの未解決問題があり、そのほとんどの未解決問題に対して解決への道筋すら確立されていません。これまでの私の研究で、平均時計算量に関する未解決問題に関して進展を与えたことが評価され、嬉しく思います。しかしながら、私の目指す最終的なゴールに到達するまでにはまだまだ道のりは長いと感じています。究極的には、公開鍵暗号方式の安全性を証明することによって、我々の情報通信社会が本当の意味で安心・安全であることを保証することを目指しています。今回の受賞を励みに、今後も計算量理論の未解決問題を解決し、それによって未来の社会に貢献することを目指して日々邁進していきたいと思います。