暗号学者が総合的な検索プライバシーのアプローチを考案 | クアンタマガジン

オンラインで共有する詳細には注意する必要があることは誰もが知っていますが、私たちが求めている情報は暴露的なものである場合もあります。 車での道順を検索すると、現在地を推測するのがはるかに簡単になります。 侵害されたデータの山のパスワードをチェックすると、私たち自身がパスワードを漏洩する危険があります。

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

この問題を解決する戦略 (個人情報の検索として知られる) を考案することは、「多くのプライバシー保護アプリケーションにおいて非常に有用な構成要素である」と同氏は述べています。 デビッド·ウー、テキサス大学オースティン校の暗号学者。 1990 年代以来、研究者たちはこの問題に少しずつ取り組み、データベースにプライベートにアクセスするための戦略を改善してきました。 大きな目標の XNUMX つは、大規模なデータベースではまだ不可能ですが、Google のプライベート検索に相当するもので、大規模な計算を行うことなく、匿名で大量のデータをふるいにかけることです。

現在、XNUMX人の研究者が 細工された 個人情報検索の長い間求められていたバージョンであり、より一般的なプライバシー戦略を構築するためにそれを拡張しました。 を受賞した作品は、 最優秀論文賞 XNUMX月の年次総会で コンピューティング理論に関するシンポジウム、真にプライベートな検索に至るまでの大きな理論的障壁を打ち破ります。

「これは、誰もが望んでいたものの、その存在を完全には信じていなかった暗号技術の何かです」と氏は述べた。 ヴィノド・ヴァイクンタナサン、マサチューセッツ工科大学の暗号学者でしたが、この論文には関与していませんでした。 「これは画期的な結果です。」

プライベート データベース アクセスの問題は 1990 年代に明らかになりました。 当初、研究者らは、唯一の解決策は検索のたびにデータベース全体をスキャンすることだと考えていました。これは、本を持って帰る前に図書館員にすべての棚を調べてもらうようなものです。 結局のところ、検索でセクションがスキップされた場合、図書館員はあなたの本が図書館のそのセクションにないことを知ることになります。

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

2000 年代初頭、研究者はデータベースを「前処理」することでフルスキャンの障壁を回避できるのではないかと考え始めました。 これは、大まかに言うと、データベース全体を特別な構造としてエンコードすることを意味し、サーバーはその構造のほんの一部を読み取るだけでクエリに応答できるようになります。 十分に慎重に前処理を行うと、理論的には、情報をホストする単一サーバーがそのプロセスを単独で XNUMX 回だけ実行することになり、将来のすべてのユーザーがそれ以上の労力を必要とせずに情報を非公開で取得できるようになります。

ダニエル・ウィックス、ノースイースタン大学の暗号学者であり、新しい論文の共著者である彼は、それが真実であるにはあまりにも良いことのように思えました。 2011 年頃、彼はこの種の計画が不可能であることを証明しようと試み始めました。 「そんなことはできるわけがないと確信していました」と彼は語った。

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

そのため、ウィックス氏は希望を新たにしたものの、これらのプログラムのバージョンが安全になるのはまだ遠い先のことだと考えていました。 その代わりに、彼とその共著者たちは — ウェイカイ・リン、現在はバージニア大学に在籍しており、 イーサン・ムック、ノースイースタンでも、複数のサーバーがデータベースをホストするケースを含む、より簡単だと思われる問題に取り組みました。

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

この方法では何の改善も得られず、グループは諦めかけましたが、このツールが待望の単一サーバーの場合に実際に機能するかどうか疑問に思うまでになりました。 十分に慎重に多項式を選択すれば、2011 年の結果に基づいて XNUMX 台のサーバーで多項式を前処理できることがわかり、ウィックス氏が長年考えていた安全で効率的な検索スキームが得られました。 結局のところ、彼らは突然、より難しい問題を解決したのです。

最初、著者たちはそれを信じませんでした。 「これの何が問題なのか考えてみよう」とウィックス氏は考えたのを覚えている。 「私たちはどこで故障するのかを突き止めようと努力し続けました。」

しかし、解決策は成り立ちました。彼らは、単一サーバーのデータベースを前処理する安全な方法を本当に発見し、誰でも秘密裏に情報を引き出すことができたのです。 「それは私たちが期待していたすべてを本当に超えています」と彼は言いました ユヴァル・アイシャイ、イスラエルのテクニオンの暗号学者であり、この研究には関与していませんでした。 これは「我々が求める勇気すらなかった」結果だという。

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

典型的な準同型暗号化戦略は、個人情報の取得と同じ問題に遭遇し、検索のたびにインターネットのすべてのコンテンツをゆっくりと調べてしまいます。 しかし、著者らは、プライベート ルックアップ手法を足場として使用して、私たちが毎日使用するプログラムによく似た計算を実行し、インターネット全体を掃除することなく秘密裏に情報を引き出す新しいスキームを構築しました。 これにより、インターネット検索やデータへの迅速なアクセスが必要なプログラムの効率が向上します。

イシャイ氏は、準同型暗号はプライベートルックアップスキームの有用な拡張である一方、プライベート情報の検索がより根本的な問題であると考えていると述べた。 著者らのソリューションは「魔法のビルディング ブロック」であり、準同型暗号化戦略は自然なフォローアップです。

今のところ、どちらのスキームも実用的ではありません。現在、前処理は、データベース サイズが無限に向かって膨れ上がる極端な場合に役に立ちます。 しかし、実際に導入すると、そのような節約は実現できず、そのプロセスにより多くの時間とストレージ スペースが消費されてしまいます。

幸いなことに、暗号学者には、当初は実用的ではなかった結果を最適化してきた長い歴史がある、とヴァイクンタナタン氏は語った。 今後の取り組みによってこのアプローチが合理化されれば、巨大なデータベースからのプライベート検索が実現できるかもしれないと同氏は考えている。 「私たちは皆、そこで立ち往生していると思っていました」と彼は言いました。 「ダニエルの結果が与えるものは希望です。」

クアンタ では、視聴者により良いサービスを提供するために一連のアンケートを実施しています。 私たちのものを取ってください コンピュータサイエンス読者アンケート そしてあなたは無料で当選するためにエントリーされます クアンタ 商品。