コンピュータ科学者が暗号の「最高傑作」を達成

2018年、カリフォルニア大学ロサンゼルス校の大学院生であるアーユシュ・ジェインは、彼と同僚が開発中の強力な暗号ツールについて講演するために日本を訪れました。彼がチームの識別不能性難読化（略してiO）へのアプローチを詳しく説明していたとき、聴衆の一人が困惑した様子で手を挙げました。

「でも、iOは存在しないと思っていたのですが？」と彼は言いました。

当時、そのような懐疑論が広く蔓延していました。識別不能性難読化が実現できれば、データの集合だけでなくコンピュータプログラム自体の内部構造も隠蔽でき、ほぼすべての暗号プロトコルを構築できるような、いわば暗号のマスターツールが完成することになります。ハーバード大学のボアズ・バラクは、これは「すべてを支配する唯一の暗号プリミティブ」だと述べました。しかし、多くのコンピュータ科学者にとって、まさにこの力こそがiOの素晴らしさを現実離れしたものに感じさせました。

コンピュータ科学者たちは2013年からiOの候補バージョンを発表し始めました。しかし、これらの構築が生み出した熱狂は、他の研究者がセキュリティを破る方法を発見するにつれて、徐々に冷めていきました。攻撃が積み重なるにつれて、「多くのネガティブな雰囲気が見られるようになりました」と、イスラエルのハイファにあるテクニオンのユヴァル・イシャイ氏は述べています。研究者たちは「勝つのは誰だ？作る者か、破る者か？」と疑問を抱いていたと彼は言います。

「熱狂的な信者たちがいて、iOを信じて開発を続けていました」と、カリフォルニア大学バークレー校シモンズ計算理論研究所所長のシャフィ・ゴールドワッサー氏は語る。「しかし、年月が経つにつれて、そういう人たちはどんどん減っていきました」と彼女は言う。

ジェイン氏は現在、ワシントン大学のホイジア・リン氏、そしてUCLAでジェイン氏の指導教官を務めるアミット・サハイ氏とともに、開発者たちに警鐘を鳴らしている。8月18日にオンライン投稿された論文で、3人の研究者は「標準的な」セキュリティ仮定のみを用いて、識別不能性難読化を構築する方法を初めて示した。

すべての暗号プロトコルは仮定に基づいています。有名なRSAアルゴリズムのように、標準的なコンピュータでは2つの大きな素数の積を素早く解くことは決してできないという、広く信じられている考えに基づいているものもあります。暗号プロトコルの安全性はその仮定に基づいており、これまでのiOの試みは、検証されていない、そして最終的には不安定な基盤の上に構築されていました。これとは対照的に、新しいプロトコルは、過去に広く使用され、研究されてきたセキュリティの仮定に基づいています。

「本当に驚くべき展開がない限り、これらの想定は維持されるだろう」とイシャイ氏は述べた。

このプロトコルは現実世界のアプリケーションに導入できる段階には程遠いですが、理論的な観点からは、これまで実現不可能だった様々な暗号ツールを即座に構築できる手段を提供します。例えば、「否認可能」な暗号化（攻撃者に実際に送信したメッセージとは全く異なるメッセージを送信したと思わせることが可能）や、「機能的」な暗号化（特定のユーザーに異なるレベルのアクセス権限を与え、データを使った計算を実行できる）の作成が可能になります。

この新たな結果は、iO懐疑論者を完全に黙らせるはずだとイシャイ氏は述べた。「これで、区別不能性難読化の存在に疑問の余地はなくなるでしょう。まるでハッピーエンドのようです」

クラウンジュエル

コンピュータ科学者たちは何十年もの間、コンピュータプログラムを難読化し、内部の秘密を解読されることなく使えるようにする、安全で包括的な方法があるのではないかと考えてきました。プログラムの難読化は、多くの有用なアプリケーションを可能にします。例えば、難読化されたプログラムを使えば、銀行口座やメールアカウント内の特定のタスクを他の人に委任することができます。その際、誰かがプログラムを本来の用途以外に使用したり、アカウントのパスワードを読み取ったりする（プログラムがパスワードを出力するように設計されていない限り）ことを心配する必要はありません。

しかし、これまでのところ、実用的な難読化ツールを開発する試みはすべて失敗している。「実際に公開されたものは、滑稽なほど破られており、通常は公開後数時間以内に破られてしまう」とサハイ氏は述べた。せいぜい、攻撃者にスピードバンプを提供する程度だと同氏は述べた。

2001年には、理論面でも悪い知らせがもたらされた。最も強力な難読化は不可能だというのだ。ブラックボックス難読化と呼ばれるこの難読化では、攻撃者はプログラムを実行し、その出力を見ることで観察できる情報以外、プログラムについて全く何も知ることができない。バラク、サハイ、そして他の5人の研究者たちは、一部のプログラムは非常に頑固に秘密を漏らしてしまうため、完全に難読化することが不可能であることを示した。

しかし、これらのプログラムは難読化を回避できるように特別に作られており、現実世界のプログラムとはほとんど類似点がありません。そこでコンピュータ科学者たちは、実現可能な程度に弱く、かつ人々が実際に関心を持つような秘密を隠すのに十分な強度を持つ、別の種類の難読化が存在するのではないかと期待しました。ブラックボックス難読化が不可能であることを示した同じ研究者たちが、論文の中で代替案として、識別不能性難読化を提案しました。

一見すると、iO は特に有用なコンセプトには思えません。プログラムの秘密を隠すことを要求するのではなく、同じタスクを実行する 2 つの異なるプログラムがある場合、どちらの難読化バージョンがどちらのオリジナルバージョンから派生したのか区別できないほど、プログラムを難読化する必要があるだけです。

しかし、iOは想像以上に強力です。例えば、銀行口座に関連するタスクを実行するプログラムがあるとします。そのプログラムには暗号化されていないパスワードが含まれており、プログラムを入手した誰かに攻撃されてしまう可能性があります。この場合、パスワードを隠したまま同じタスクを実行できるプログラムが存在する限り、識別不能性難読化ツールはパスワードをうまく隠蔽できるほど強力です。もしそうでなかったとしても、両方のプログラムを難読化ツールに通せば、どちらの難読化バージョンが元のプログラムから派生したものかが分かるでしょう。

長年にわたり、コンピュータ科学者たちは、iO を想像し得るほぼすべての暗号プロトコル（ブラックボックス難読化を除く）の基盤として利用できることを実証してきました。これには、公開鍵暗号（オンライン取引で利用）のような古典的な暗号タスクだけでなく、クラウドコンピュータが暗号化されたデータについて何も学習することなく計算できる完全準同型暗号のような画期的な新技術も含まれます。さらに、否認可能暗号や関数型暗号など、誰も構築方法を知らなかった暗号プロトコルも含まれます。

コーネル大学のラファエル・パス氏は、「これはまさに暗号プロトコルの最高峰と言えるでしょう」と述べた。「これを実現できれば、実質的にあらゆるものを手に入れることができるのです。」

2013年、サハイと5人の共著者は、プログラムをジグソーパズルのピースのように分割し、多重線形写像と呼ばれる暗号オブジェクトを用いて個々のピースを文字化けさせるiOプロトコルを提案した。ピースが正しく組み合わされれば文字化けは解消され、プログラムは意図したとおりに動作するが、個々のピースは無意味に見える。この成果は画期的な成果として歓迎され、数十本の論文が発表された。しかし数年後、他の研究者らが、文字化け処理に用いられる多重線形写像が安全ではないことを示してしまった。他のiO候補が登場し、それらも次々と破られた。

「もしかしたらこれは単なる幻かもしれない、iOは単に入手不可能なのかもしれない、という懸念もありました」とバラク氏は語った。人々は「もしかしたらこの事業全体が破綻するかもしれない」と感じ始めたと彼は語った。

隠すことを減らすことで、より多くを隠す

2016年、リン氏は多重線形写像の弱点を、単にそれらへの要求を少なくすることで回避できるかどうかを探り始めました。多重線形写像とは、本質的には多項式を用いた計算を秘密裏に行う方法に過ぎません。多項式とは、3 xy + 2 yz ²のように、数値と変数の和と積からなる数式です。ジェイン氏によると、これらの写像は、変数の値を格納した秘密のロッカーシステムに接続された多項式計算機のようなもので、計算機が受け入れる多項式を入力するユーザーは、最後のロッカーの中を見て、隠された値によって多項式の評価が0になるかどうかを調べることができます。

この方式が安全であるためには、ユーザーは他のロッカーの中身や、その過程で生成された数値について何も知ることができないようにする必要がある。「そうなってほしい」とサハイ氏は述べた。しかし、人々が思いついたすべての多重線形写像の候補において、最後のロッカーを開ける過程で、本来は隠されているはずの計算に関する情報が明らかになった。

提案された多重線形写像マシンはすべてセキュリティ上の弱点を抱えていたため、リンは、それほど多くの種類の多項式を計算する必要のないマシン（したがって、より安全に構築しやすいマシン）を使ってiOを構築する方法があるのではないかと考えました。4年前、彼女は「次数」が30以下の多項式を計算する多重線形写像のみを使ってiOを構築する方法を発見しました（つまり、各項は繰り返しを含めて最大30個の変数の積であるということです）。その後数年間、リンとサハイ、そして他の研究者たちは、次数をさらに下げる方法を徐々に見つけ出し、最終的に次数3の多重線形写像のみを使ってiOを構築する方法を示すことができました。

理論上は大きな進歩のように見えた。しかし、一つだけ問題があった。セキュリティの観点から見ると、「3次式は、あらゆる次数の多項式を処理できるマシンと同じくらい壊れていた」とジェイン氏は述べた。

研究者たちが安全に構築できる多重線形写像は、2次以下の多項式を計算するものだけだった。リンはジェインとサハイと協力し、2次多重線形写像からiOを構築する方法を見つけ出そうとした。しかし「私たちは非常に長い間行き詰まっていました」とリンは語った。

「ちょっと暗い時期でした」とサハイは回想する。「うまくいかなかったアイデアが詰まった墓場みたいな感じでした」

しかし結局、カリフォルニア大学サンタバーバラ校の Prabhanjan Ananth 氏とブロックチェーンプロジェクト Concordium の Christian Matt 氏とともに、ある種の妥協案を思いつきました。iO には次数 3 のマップが必要なようですが、コンピューター科学者は次数 2 のマップに対してしか安全な構成がなかったので、その中間、つまり次数 2.5 のマップのようなものがあったらどうなるでしょうか。

研究者たちは、ロッカーの一部に透明な窓を設け、ユーザーが中に入っている値を見ることができるシステムを構想しました。これにより、マシンは過剰な隠蔽情報を保護する必要がなくなります。高次多重線形写像の威力と2次写像のセキュリティのバランスを取るため、マシンは2次以上の多項式で計算できますが、制約があります。多項式は隠れ変数に対して2次でなければなりません。「一般的な多重線形写像ほど多くの情報を隠蔽しないようにしています」とリン氏は述べています。研究者たちは、これらのハイブリッドロッカーシステムを安全に構築できることを実証することができました。

しかし、これらのそれほど強力ではない多重線形写像からiOに到達するには、研究チームは最後の要素を必要としました。それは、ランダムなビット列を、コンピューターを騙すのに十分なランダム性を保ちつつ、より長い文字列に拡張する、新しい種類の疑似乱数生成器です。ジェイン、リン、そしてサハイは、新しい論文でその方法を発見しました。「ここ1ヶ月ほど、電話のやり取りですべてがうまくまとまった素晴らしい時間がありました」とサハイは語りました。

その結果、多重線形写像のセキュリティ上の弱点を最終的に回避するiOプロトコルが誕生しました。「彼らの仕事は本当に素晴らしいです」とパス氏は語りました。

この方式の安全性は、他の暗号分野で広く用いられている4つの数学的仮定に基づいています。そして、最も研究が進んでいない「ノイズ付き学習パリティ」仮定でさえ、1950年代から研究されてきた問題に関連しています。

この新しい方式を破ることができるのは、おそらく一つだけだろう。それは、もしフルパワーの量子コンピュータが実現すればの話だが、量子コンピュータだ。4つの前提のうち1つは量子攻撃に対して脆弱だが、ここ数ヶ月の間に、パス氏ら研究者による3本の別々の論文が発表され、量子攻撃に対しても安全かもしれないiOへの別の可能性が示唆されている。複数の研究者によると、これらのiOのバージョンは、ジェイン氏、リン氏、サハイ氏が用いたものよりも確立されていないセキュリティ前提に基づいている。しかし、バラク氏によると、今後数年のうちにこれら2つのアプローチを組み合わせ、標準的なセキュリティ前提に基づきつつ量子攻撃にも耐性を持つiOのバージョンを開発できる可能性があるという。

ジェイン、リン、そしてサハイによる建設は、この分野に新たな研究者を惹きつけ、この計画をより実用化し、新たなアプローチを開発する研究に参入させるだろうとイシャイは予測した。「原理的に何かが可能だと分かれば、この分野で研究するのが心理的にずっと楽になります」と彼は言った。

このプロトコル（もしくはその派生形）が現実世界のアプリケーションで利用できるようになるまで、コンピュータ科学者はまだ多くの研究をしなければならない。しかし、それは当然のことだと研究者たちは言う。「暗号技術には、最初に登場した時には『これは単なる理論で、実用には無関係だ』と言われていた概念がたくさんあります」とパス氏は言う。「それから10年、20年後、Googleはこれらの概念を実装しているのです。」

理論的なブレークスルーから実用的なプロトコルへの道のりは長いかもしれないとバラク氏は述べた。「しかし、50年後には暗号の教科書に『これがiOの非常にシンプルな構成だ。そこから暗号の残りのすべてを導き出そう』と書かれているかもしれない、と想像できるでしょう」と彼は言った。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事

📩 テクノロジー、科学、その他の最新情報を知りたいですか？ニュースレターにご登録ください！
名もなきハイカーとインターネットでは解明できない事件
海軍特殊部隊SEALs、ドローン、そして戦闘で命を救うための探求
古いガジェットを再利用する方法
「悪魔のような」カブトムシが車に轢かれても生き残る方法
なぜ誰もが電気ピックアップトラックを作っているのでしょうか?
🎮 WIRED Games: 最新のヒントやレビューなどを入手
🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください