暗号学者は完全にプライベートなインターネット検索の実現に近づいている

この物語 のオリジナル版はQuanta Magazineに掲載されました。

オンラインで共有する情報には注意が必要だと誰もが認識していますが、私たちが求める情報の中には、個人情報を漏洩してしまうものも存在します。運転ルートを検索すると、自分の居場所を推測されやすくなります。また、漏洩した大量のデータの中からパスワードを探すと、自分自身が漏洩してしまうリスクがあります。

こうした状況は、暗号学における重要な疑問を提起します。アクセスした情報を一切明かさずに、公開データベースから情報を引き出すにはどうすればよいのでしょうか？これは、司書がどの本なのかを知らないまま図書館から本を借りるのと同じです。

この問題を解決する戦略（いわゆる「プライベート情報検索」）を考案することは、「多くのプライバシー保護アプリケーションにおいて非常に有用な構成要素となる」と、テキサス大学オースティン校の暗号学者デビッド・ウー氏は述べています。1990年代以降、研究者たちはこの問題に着手し、データベースへのプライベートアクセス戦略を改良してきました。大きな目標の一つは、大規模なデータベースでは依然として実現不可能ですが、プライベートなGoogle検索に相当するものを実現することです。つまり、膨大なデータを匿名で、しかも膨大な計算処理をすることなくふるいにかけることです。

今回、3人の研究者が、長年待ち望まれていたプライベート情報検索の新たなバージョンを開発し、それを拡張してより汎用的なプライバシー戦略を構築しました。この研究は、2023年6月に開催される年次シンポジウム「コンピューティング理論シンポジウム」において最優秀論文賞を受賞し、真にプライベートな検索を実現する上で大きな理論的障壁を打ち破りました。

「これは暗号技術において、誰もが望んでいたものの、実際に存在するとは信じられなかったものだと思います」と、マサチューセッツ工科大学の暗号学者、ヴィノド・ヴァイクンタナサン氏は述べた。同氏はこの論文には関わっていない。「画期的な成果です。」

プライベートデータベースへのアクセス問題は1990年代に顕在化しました。当初、研究者たちは唯一の解決策は検索のたびにデータベース全体をスキャンすることだと考えていました。これは、図書館員があなたの本を返却する前にすべての棚をくまなく調べるようなものでした。検索で特定のセクションが飛ばされれば、図書館員はあなたの本がそのセクションにないことに気付いてしまうからです。

このアプローチは小規模なデータベースでは十分に機能しますが、データベースが大きくなるにつれて、スキャンに必要な時間も少なくとも比例して長くなります。大規模なデータベース（インターネットはかなり大規模なものです）から読み取る場合、このプロセスは法外なほど非効率になります。

2000年代初頭、研究者たちはデータベースを「前処理」することでフルスキャンの障壁を回避できるのではないかと考え始めました。これは大まかに言えば、データベース全体を特別な構造としてエンコードし、サーバーがその構造のごく一部を読み取るだけでクエリに応答できるようにすることを意味します。十分に綿密な前処理を行えば、理論上は、情報をホストする単一のサーバーがこのプロセスを一度だけ実行するだけで、将来のユーザーはそれ以上の手間をかけずに情報をプライベートに取得できるようになります。

ノースイースタン大学の暗号学者で、今回の論文の共著者でもあるダニエル・ウィックス氏にとって、それはあまりにも出来すぎた話に思えた。2011年頃、彼はこの種の計画が不可能であることを証明しようと試み始めた。「絶対に不可能だと確信していました」と彼は語った。

しかし2017年、2つの研究グループが彼の考えを変える結果を発表しました。彼らはこの種の個人情報検索が可能な最初のプログラムを構築しましたが、そのプログラムの安全性を証明することはできませんでした。（暗号学者は、システムのセキュリティを、それを破ることが難問を解くのと同じくらい難しいことを示すことで証明します。研究者たちは、それを標準的な難問と比較することができませんでした。）

希望を新たにしたにもかかわらず、ウィックスはこれらのプログラムの安全なバージョンが実現するのはまだ遠い先のことだと考えていた。そこで、彼と共著者であるウェイカイ・リン（現在はバージニア大学）、イーサン・ムック（同じくノースイースタン大学）は、より容易と思われる問題、つまり複数のサーバーがデータベースをホストしているケースに取り組んだ。

彼らが研究した手法では、データベース内の情報は数式に変換され、サーバーはそれを評価することで情報を抽出できます。著者らは、この評価プロセスをより効率的にできるのではないかと考えました。彼らは2011年に、他の研究者が数式を前処理することで迅速に評価する方法を発見し、特別なコンパクトな値テーブルを作成することで通常の評価手順を省略するというアイデアを考案しました。

この方法では何の改善も見られず、研究チームは諦めかけていた。ところが、このツールが念願の単一サーバーの場合にも実際に機能するのではないかと考え始めた。多項式を慎重に選べば、単一サーバーで2011年の結果に基づいて前処理できることが判明したのだ。こうして、ウィックス氏が長年考え続けてきた安全で効率的な検索方式が実現した。そして、ついに彼らは、より困難な問題を解決したのだ。

当初、著者たちはそれを信じなかった。「一体何が問題なのか考えてみよう」とウィックス氏は思ったことを覚えている。「どこで問題が起こっているのかを突き止めようとし続けたのです」

しかし、解決策は有効だった。彼らは、単一サーバーのデータベースを前処理する安全な方法を実際に発見したのだ。これにより、誰でも秘密裏に情報を引き出すことが可能になったのだ。「これは我々の期待をはるかに超える成果です」と、この研究には関与していないイスラエル工科大学の暗号学者、ユヴァル・イシャイ氏は述べた。「これは我々が求める勇気さえなかった成果です」と彼は語った。

秘密検索スキームを構築した後、著者らは現実世界の目標であるプライベートインターネット検索に着手した。これはデータベースから少量の情報を引き出すよりも複雑だとウィックス氏は述べた。このプライベート検索スキーム自体は、Googleのようなプライベート検索を可能にするが、非常に手間がかかる。Googleのアルゴリズムを自分で実行し、必要に応じてインターネットから秘密裏にデータを引き出す必要があるからだ。ウィックス氏によると、リクエストを送信し、サーバーが結果を収集するのを待つだけの真の検索は、準同型暗号と呼ばれるより広範なアプローチのターゲットとなる。準同型暗号は、データを偽装することで、第三者がデータについて何も知らずに操作できるようにするものだ。

典型的な準同型暗号戦略は、検索のたびにインターネット上のすべてのコンテンツを調べる必要があり、プライベート情報検索と同じ問題に直面するでしょう。しかし、著者らは、プライベート検索手法を足場として、私たちが日常的に使用するプログラムに近い計算を実行する新しい方式を構築しました。インターネット全体を網羅することなく、秘密裏に情報を取得します。これにより、インターネット検索や、データへの迅速なアクセスを必要とするあらゆるプログラムの効率が大幅に向上するでしょう。

イシャイ氏は、準同型暗号は秘密検索方式の有用な拡張ではあるものの、個人情報の取得こそがより根本的な問題だと考えていると述べた。著者らの解決策は「魔法の構成要素」であり、彼らの準同型暗号戦略はそこから自然に派生したものである。

現時点では、どちらの方式も実用的ではありません。前処理は、データベースのサイズが無限大に膨れ上がるような極端な状況では役立ちますが、実際に導入すると、こうした節約効果は実現できず、処理に膨大な時間とストレージ容量が消費されてしまいます。

ヴァイクンタナサン氏によると、幸いなことに暗号学者たちは、当初は非現実的だった結果を最適化してきた長い歴史を持っているという。今後の研究でこのアプローチが合理化されれば、巨大データベースからのプライベート検索も実現可能になるかもしれないと彼は考えている。「私たちは皆、そこで行き詰まっていると思っていました」と彼は言った。「ダニエル氏の結果は希望を与えてくれます。」

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