FrodoPIR：データ取得に関する新しいプライバシー保護の取り組み

執筆: Sofía Celi(Brave暗号技術研究者)、Alex Davidson(元Brave暗号技術研究者)、Gonçalo Pestana(元Brave暗号技術研究者)

信頼 できない サーバーに存在するデータベースに対してどのようなクエリが使われているかわからない状況で、どのようにして必要な情報を取得するか。コンピュータサイエンスにおけるセキュリティとプライバシーに関する興味深い問題の1つにこのようなものがあります。今日は様々なアプリケーションで生じるこのような問題を解決するために、Braveが行った最近の研究についてお伝えします。

私たちは、FrodoPIRと呼ばれる新しいプライバシー情報保護（Private Information Retrieval/PIR）スキームを構築しました。このスキームにより、セーフブラウジング、不正なデータベース上でのパスワードチェック、証明書の失効チェック、ストリーミングなど、様々なユースケースやアプリケーションでPIRをより簡単に、より安価に展開することができるようになると期待しています。現在、オープンソースの実装を公開しており、論文も公開しています。この論文はPoPETS 2023の創刊号に採択されました！このスキームをFrodoPIRと呼んでいます。FrodoがSauronから隠れたように(日本語訳注：ロードオブザリングになぞらえた例えです)、クライアントもサーバーに対して隠れたクエリ送信を行うことができるからです。

プライベート・データベース・アクセス概論

データベースからアイテムを取得する際に、なぜプライバシーの問題が重要なのでしょうか。例えば、あなたがお気に入りのストリーミング・プラットフォームで、犬のビデオを見たいとします。しかし実際のところ、自分が犬の動画を何本見ているのか、プラットフォームに監視されるのは少し恥ずかしいと思うでしょう（監視されるべきではありませんが、それがこの世界の現実です）。そしてそのデータを悪用されて、例えばターゲット広告キャンペーンに利用されるのも避けたいところでしょう。あなたがストリーミングしているものが何であるかを信頼できないプロバイダーに知られることなく、コンテンツを受け取ることができれば、それは素晴らしいことです。

PIR（Private Information Retrieval） スキームは、この問題を解決するために提案された暗号プロトコルの一種です。多くの暗号と同様、最初の方式は1990年代に登場しましたが、現代のユースケースに対応できるような高性能な方式が設計されるようになったのは、ここ6、7年のことです。多くの方式は、低帯域幅やサーバー実行時間を現実的なものにするために非常に特殊なユースケースに合わせて調整されており、PIRクエリを実行するために複雑なサーバー側の配置（例えば、少なくとも2つの非凝集サーバーを使用するなど）が必要な場合があります。

それらを踏まえて私たちは FrodoPIR を作りました！今回発表するこの新しいPIR方式は、非常に柔軟な設定が可能で、様々なアプリケーションで効率的に利用でき、理解も実装も簡単で、必要なのはデプロイを行う信頼されていないサーバ1台で、（後述しますが、格子(lattices)を用いているため）古典的・量子敵対者(classical and quantum adversaries)に対するプライバシーとセキュリティに対する保証を備えています。

PIR：一般的な考え方

おおまかなところでは、ほとんどの単一サーバPIRスキームは、相加相同暗号化（AHE）という暗号化ツールを使用します。この暗号化方式では、XとYを暗号化した二つの暗号文を持っている人が、秘密鍵を知らなくてもX+Yを暗号化した暗号文を作ることができるのです。このような方式はRSA以来存在していますが、よく使われているのはPaillier暗号方式です。

図1: AHEシステム

しかし、このようなものからどのようにPIRプロトコルを構築すればよいでしょうか。図1に見られるように、その答えは驚くほどシンプルです。

1. サーバはデータベースをM行の集合に編成し、それぞれが1つの要素を含みます。つまり、データベースはベクトルになります。
2. i番目の要素を知りたいクライアントは、M個の暗号文を暗号化します。ここで、i番目の暗号文は1を暗号化し、残りの暗号文は0を暗号化します。
3. クライアントはその暗号文をサーバーに送信します。暗号の性質上、サーバーは何が暗号化されているかを知ることはできません。
4. サーバは、そのデータベース・ベクトルの各エントリ db_entry_1,…,db_entry_M に対して、それぞれに対応する暗号文とのスカラー倍算を行い、それらをまとめて一つの暗号文にし、これをクライアントに返します。スカラー倍算は、スカラーの大きさに応じて各暗号文を自分自身に加算することで可能であることに注意してください。
5. 考え方としては 0db_entry_1,…,1db_entry_i,…,0*db_entry_M = db_entry_i となります。クライアントはそれぞれの暗号文を復号した後、シンプルに db_entry_i を知ることになります。

基本的には、過去数年にわたり、この単純な方法（およびいくつかの最適化）を用いて、PIRを非常に効率的に構築できることが示されてきました。これは、暗号格子に基づくAHE方式、特に完全な準同型暗号（fully homomorphic encryption/FHE）方式を用い、Ring Learning with Errors（RLWE）仮定に基づく安全性を確保することで実現されています。

これらについては、追ってもう少し詳しく説明しますが、その前にいくつか注意事項があります。

• 複数のサーバーでPIRを構成する方が効率が良いのですが、サーバーが共謀しないという前提が必要になります。このような前提は強固な環境をつくるためには必要であることが知られており、できる限り排除することが望まれます。
• サーバは「正直で興味津々」なものです。プロトコルを正直に実行しますが、独自にクライアントクエリからより必要以上に学ぼうともします。悪意のあるサーバーは、PIRプロトコルを正しく実行しないことを選択することができ、するとクライアントは不正な返答を得ることになります。
• サーバーのデータベースは公開されていることが前提です。もし、データベースが機密扱いとなる（つまり、クライアントがクエリ以外の情報を得られない）ならば、PIRは本当に正しいツールではありません（ただし、これに対する洞察を提示する対称的なPIR構造もあります）。

既存アプローチの制限事項

私たちはPIRを使って、サーバーに気づかれずにクライアントがBraveから何かを取得することに関心を持つようになりました。しかし、既存のシステムをいろいろと試してみたものの、膨大なコストや実装の複雑さをを排除してそのような実装をすることはできませんでした。そこで、これらの要件に少しでも合うPIRの仕組みを作れないかと考え、新しいアプローチを作り始めたのです。それがFrodoPIRです。では、既存の手法の限界は何なのかを考えてみましょう。

かなり最近のPIR方式にも生じる共通の問題は、帯域幅を必要とすることや、各クライアントのクエリ処理に時間がかかることなど、様々なコストが生じることです。コストを下げるために、FHEベースのPIRスキームは、高コストなオンラインの計算や通信（例えば、クエリの送信）の大部分をオフラインフェーズ（後でオンラインクエリを作るために再利用できる「準備」フェーズ）に移行することができます。この種の方式は、オンライン・オンリー/ステートレスと対比して、オフライン-オンライン/ステートフルと呼ばれています。

しかし、オフラインフェーズで発生する計算コストや通信コストは、クエリを実行するクライアント数に比例して増加するか、クライアントがサーバのデータベース全体をダウンロードしなければならないこと（これでは目的から外れてしまいます）が、未解決な問題点として残っています。つまり、オフラインフェーズは各クライアントとサーバーの間で実行されなければならず、原理的には、サーバーが実行しなければならない高コストな処理がたくさんあるのです。もし、市販のハードウェアを使ってサーバーを稼動させるのであれば、これらのコストは莫大な金銭的コストになる可能性があります。

FrodoPIR登場！

Sauronの状態（指輪）がFrodoに移動したように、muとAをクライアントに移動させることができます。そしてクライアントは、FrodoがSauronから隠れたままであるように、サーバーに対して秘密のクエリを行うことができるのです。

私たちは、FrodoPIRを紹介できることを嬉しく思います。これは、LWE（learning with errors）問題に着目して構築されたステートフルPIRスキームです。我々は、様々なユースケースに対応する柔軟で実用的なPIR方式を実現するために、リング 格子構造を取り除きました(リングはFrodoに必要です：Frodoがはじめに引用されたのはFrodoKEM proposalでした。そして現在は私たちもFrodoを引用しています)。FrodoPIRの中核は、クライアント依存の計算を必要とせず、データベースサイズと比較して比較的小さな（約1/170程度の）ダウンロードしか発生しないオフラインフェーズです。これは、サーバー側の運用コストを下げることが最も重要である多くの大規模なデプロイに適しています。また、FrodoPIRは、FHE技術を使用せず、モジュール演算のみを必要とするため、従来の方式よりも大幅にシンプルになりました。本論文の全文はこちらでご覧いただけます。

FrodoPIRは、決定論的LWE問題に基づいた方式であり、各クライアントのクエリは、サーバに対しては一律にランダムでノイジーなベクトルとなります。前述しましたが、この方式にはオフラインとオンラインの両方のフェーズがあります。

図2: FrodoPIRのフロウダイアグラム

1. オフラインフェーズでは、サーバーはデータベースを行列として解釈し、その行列に圧縮関数を適用し、その結果をグローバルな公開パラメータ（muとM）として利用できるようにします。この圧縮機能により、データベースのサイズが縮小されます。
2. また、オフラインフェーズではクライアントは公開パラメータ（muとM）をダウンロードし、前処理されたクエリパラメータの「c」セットを計算します。
3. オンラインフェーズでは、クライアントは前処理されたクエリパラメータセット使用して「暗号化」されたクエリベクトルを生成し、サーバに送信します。
4. サーバーはこのベクトルとデータベースの行列を掛け合わせることでクエリに応答します。
5. クライアントは、前処理されたクエリパラメータを用いてレスポンスを「復号化」して結果を確認します。

要するに、オフラインフェーズでは、サーバーとクライアントはオンラインクエリのために事前に準備できるものはすべて準備し、オンラインフェーズでは、クライアントがサーバーに暗号化されたクエリを送信するのです。後者は、そのクエリがデータベース内で見つかったかどうかによって、正または負の値を返します。サーバーは、どの値に対して問い合わせをしているのかを知ることはなく、正しい答え（データベースに含まれていたかどうか）を返します。

FrodoPIRは、通信コストや計算コストだけでなく、金銭的なコストも重要な現実世界での利用においてPIRスキームを実用化する、強力な原動力となります。PIRは一般に強力で、セーフブラウジング、漏洩したデータベース（もしくは様々な証明書）上のパスワードチェック、証明書の透明性（CT）チェック、証明書の失効チェック、ストリーミングに適用することが可能です。安価で高効率なスキームを持つことは、大企業だけでなく、そのようなサービスを提供するすべての人が、インターネット全体のプライバシーを向上させるための手助けとなります。

注目すべきは、FrodoPIR 以外にも PIR 方式はありますが、以下の図 3 に見られるように、FrodoPIRがそれらすべてを上回っていることです。この図は、FrodoPIR、Stateful OnionPIR (SOnionPIR)、PSIRを実行した場合の、クライアントごとの計算コスト、通信コスト、サーバーの経済的コストを、各クライアントがc＝500クエリを行うと仮定して比較したものです。

図3: FrodoPIRと他のPIRスキームの比較

では次に、FrodoPIRの実装はBraveユーザーにどのようなメリットをもたらすでしょうか？Braveでは、インターネットをプライベートで安全なものにするために、プライバシーを保護するスキームを展開することに注力しています。私たちの次なる展開はクリデンシャル・チェッカーです。Braveのブラウザから入力されるあらゆるクリデンシャル（パスワードなど）を、漏洩が判明したデータベースに対して安全に照合できるようになります。これは、(例えばパスワード変更を促す)ユーザー通知の安全なメカニズムとして活用できます。しかし、このようなチェック（漏洩したデータベースに対して起動されるクエリー）は非公開であるべきです。この点で、FrodoPIRは、経済的に安価で、効率的に速い方法でプライバシーを提供するメカニズムとして優れているのです。

FrodoPIRスキームの詳細については、こちらをご覧ください。本論文は、Proceedings on Privacy Enhancing Technologies (PETS), Vol.2023, Issue 1に採択され、こちらにも掲載される予定です。