本記事は MIT Newsとの協力により掲載されています。
「識別不能難読化」は、これまでに開発されたすべての暗号システムと、まだ開発できていないすべての暗号システムについて、証明可能な安全性を持つ版をもたらしうる強力な概念である。しかし、それを実際に実現する方法は誰にもわかっていない。
先週開催されたIEEEコンピュータ科学基礎シンポジウムで、MITの研究者らは、識別不能難読化の問題が実は、効率的な 機能的暗号と呼ばれる別の暗号問題の変種であることを示した。また、計算機科学者らは効率的な機能的暗号の構築方法もまだ知らないものの、その実現に近づいていると考えており、その近さは、識別不能難読化について以前想定していたよりもはるかに近い。
「この分野は難読化よりも長い期間研究されてきており、より優れた機能的暗号方式を実現する成果が非常に順調に積み重ねられてきました」と、MITのコンピュータ科学・人工知能研究所のポスドク研究員で、電気工学・コンピュータ科学のVinod Vaikuntanathan准教授とともに学会論文を執筆したNir Bitanskyは語る。「人々はこれは小さな隔たりだと考えていました。難読化はまた別の次元です。はるかに強力です。そこには巨大な隔たりがあります。私たちがしたことは、この隔たりを本当に狭めたことなのです。今、難読化を実現し、想像しうるあらゆる暗号を標準的な仮定から得たいのであれば、必要なのは、機能的暗号をほんの少しだけ効率化するという、この非常に特定の問題を解くことだけです。」
コンピュータサイエンスにおいて、「難読化」とは、コンピュータプログラムの動作の詳細を、リバースエンジニアリングできないように偽装することを意味する。多くの難読化技術が提案されてきたが、その多くが破られてきた。
そこで計算機科学者らは、この考えを理論的に検討し始めた。理想的な難読化方式は、プログラムのソースコードを受け取り、それが動作するプログラムを依然として生成するように書き換えるが、実行されている操作を特定することは不可能である。
理論家たちは、理想的な難読化があれば、彼らが思いつくほぼあらゆる暗号方式が可能になることをすぐに証明した。しかし、ほぼ同じ速さで、それが不可能であることも証明した。完全に難読化できないプログラムを構築する方法は、常に存在するのである。
曖昧な詳細
そこで彼らは、より緩やかな理論的原理の検討を始めた。その一つが識別不能難読化である。識別不能難読化は、攻撃者がプログラムの実行している操作について何も知りえないことを要求するのではなく、攻撃者が、実行されている操作が二つのバージョンのうちどちらであるかを判別できないことだけを要求する。
例えば、多くの人が代数から覚えているのは、 a ×(b + c)は、a × b)+(a× c)と同じであるということです。いかなる与えられた値についても、両方の式は同じ結果をもたらすが、コンピュータ上では異なる方法で実行されることになる。識別不能難読化は、攻撃者がプログラムがそれらの計算のいずれかを実行していると判定することは許されるが、どちらであるかまでは判定させない。
長年にわたり、識別不能難読化の考え方は顧みられずにいた。しかし、ここ数年で、計算機科学者らは、多重線形写像と呼ばれる数学的対象から識別不能難読化方式を構築する方法を示した。注目すべきことに、彼らは、より弱い概念である識別不能難読化であっても、暗号学のすべてをもたらしうることも示した。
しかし、多重線形写像はよく理解されておらず、それらを構築するために提案されている技術のいずれかが、識別不能難読化に求められる安全性の保証を提供するかどうかは明らかではない。
氷山の一角
一方、機能的暗号は、何十年にもわたり暗号学における人気の研究テーマであり続けてきた。これは、暗号化されたファイルに対して何らかの操作を行い、理解可能な結果を得る一方で、ファイルの内容に関するそれ以上の情報は漏らさない方法である。例えば、膨大な量の暗号化された電子メールを保存しているサーバーが、検索目的で送信者の名前だけを復号できるようにすることもできる。
標準的な暗号方式では、暗号化時間は暗号化されるファイルの長さに比例する。これこそが、BitanskyとVaikuntanathanが「効率的」という言葉で意味していることである。しかし、最良の機能的暗号方式でさえそこまで優れてはいない。その暗号化効率には、操作結果のサイズに比例する要素も含まれている。操作が送信者名の復号であれば、その要素はかなり小さいだろう。しかし原理的には、はるかに大きくなりうる。
Bitanskyは、研究者らがその余分な要素を取り除くことの難しさを過小評価していた可能性があることを認めている。「私たちの当初の見方が誤っていた可能性はあります」と彼は言う。「これはそれほど容易な問題ではないのかもしれません。これが本当の隔たりであり、解決には非常に長い時間がかかるかもしれません。しかし、私は楽観主義者です。」
「IO(識別不能難読化)に関する現在の候補となる構成は、いずれも非常に新しく、十分に理解されていない仮定に基づいており、近い将来に破られる可能性が十分にあり、実際、そのうちの多くはすでに破られています」と、コーネル大学のコンピュータ科学准教授Rafael Passは語る。「機能的暗号は、はるかに単純に見えるプリミティブであるため、この研究は、IOの安全な構成を得るための新たな道を開くものです。」
「技術的なアプローチはシンプルで美しく、他にも多くの応用があると私は予想しています」とPassは付け加える。
本記事の掲載は、世界経済フォーラムによる見解の支持を意味するものではありません。
アジェンダの最新情報を把握するには、 週刊ニュースレターにご登録ください。
著者:Larry Hardestyは、MITニュース事務局に所属しています。
画像:ノートパソコンを持つ男性に二進コードが投影された様子を示すイラスト。REUTERS/Kacper Pempel。



