TL;DR
- Private information retrieval、つまり PIR は、サーバーがどの項目を要求されたのかを知ることなく、デバイスがサーバーのデータベースから 1 つの項目を取得できるようにするものです
- Zcash にこれが必要なのは、プライベートウォレットがどのトランザクションが自分のものかをサーバーに明かさずに問い合わせることができないからです
- 現在のウォレットは必要以上にはるかに多くのデータをダウンロードしてスキャンしており、これが同期が遅い主な理由の 1 つです
- PIR があれば、ウォレットは自分に必要なデータだけをプライベートに取得できるため、プライバシーを保ったままそのボトルネックを取り除けます
- これは Zcash における活発な研究分野であり、理論上は非常に強力で、実際のウォレットで使える形へと実用化が進められています
これは誰向けか
- プライベートウォレットが、どのコインが自分のものかを漏らさずにどうやって見つけるのか疑問に思ったことがある人
- Zcash のスケーリングに関する取り組みと並んで PIR という言葉を目にし続けている初心者
- まず概念を理解し、そのあとで背後にある暗号技術を知りたい読者
PIR が Zcash で解決する問題
Zcash は、トランザクションが誰宛てかを隠します。このプライバシーによって、厄介な疑問が生まれます。ネットワークからはどのトランザクションがあなたのものか見えないなら、あなた自身のウォレットはどうやってそれを見つけるのでしょうか。
現在の答えはかなり直接的です。ウォレットはサーバーに「どのトランザクションが自分のものか」を尋ねることができません。そんな質問をすれば、まさに Zcash が隠そうとしていることを明らかにしてしまうからです。そこで代わりに、ウォレットは大量のデータをダウンロードし、それぞれの項目をローカルで検査して、自分に属するものを見つけます。これは機能しますし、プライバシーも守られますが、遅くて重い方法です。このスキャン処理は、ウォレットの同期がもっさり感じられる主な理由の 1 つです。
理想は、ウォレットがサーバーに対して自分に必要なデータだけを正確に要求し、それを受け取りつつ、サーバーは何が要求されたのかを一切知れないようにすることです。それこそが、private information retrieval が提供するものです。
PIR とは何か
Private information retrieval は、クライアントがサーバーのデータベースから 1 つのエントリを読み出しても、サーバーにはどのエントリを読んだのか分からないようにする暗号学的手法です。
たとえば図書館を想像してください。あなたは欲しい本を正確に受け取れますが、司書はどの本を渡したのか知りません。あなたは目的の品を手に入れ、何に関心があるかは秘密のままです。PIR は、この考え方をあらゆるデータベースに適用した数学的バージョンです。
この概念は、暗号学で数十年にわたって研究されてきました。最初に導入されたのは 1995 年で、Chor、Goldreich、Kushilevitz、Sudan が複数サーバー方式を説明し、最初の単一サーバーバージョンは 1997 年に Kushilevitz と Ostrovsky によって続いて提案されました。これは Zcash が発明したものではなく、Zcash が今まさに現実の、しかも根深い問題に適用している確立された分野です。
PIR の仕組みをまず大まかに
PIR を構築する方法は大きく 2 つあり、その違いは重要です。
1 つ目は複数サーバーを使う方法です。クライアントは複数のサーバーそれぞれに問い合わせの一部を送り、その答えをローカルで組み合わせます。どの単一サーバーも、何が要求されたのか学習できるほど十分な情報を見ることはありません。これは効率的ですが、サーバー同士が結託しないことに依存しており、現実世界ではそれを保証するのが難しいです。
2 つ目は、複数の主体の代わりに単一サーバーと巧妙な暗号技術を使う方法です。ここではクライアントは準同型暗号と呼ばれる特別な道具に依存します。そして、複数の非結託サーバーを必要としないため、実際の導入にもっとも有用なのはこの方向です。
仕組みの中核: 準同型暗号
準同型暗号は、データが暗号化されたままの状態でサーバーがその上で計算できるようにする暗号方式です。サーバーは基になる値を見ることなく、正しい暗号化済みの答えを生成します。
この方法で構築された単一サーバー PIR の発想は次のとおりです。クライアントはリストの中の 3 番目の項目を欲しています。そこで、実質的には「3 番目の位置には暗号化された yes」、それ以外のすべての位置には「暗号化された no」となる問い合わせを組み立てます。サーバーから見ると、この問い合わせは意味のないノイズの塊でしかなく、どの位置に yes があるのか判断できません。
次にサーバーは、準同型暗号の特別な性質を使って、この暗号化された問い合わせと自身のデータベースを組み合わせます。保存されている各項目に対応する暗号化された yes または no を掛け合わせ、その結果をすべて足し合わせるのです。すると、クライアントが欲しかった項目だけを正確に含む 1 つの暗号化パッケージが得られ、どの項目だったのかを明かす情報は何も残りません。クライアントはそのパッケージを復号して、自分の項目を読みます。サーバーは、質問そのものを知ることなく質問に答えたことになります。
さらに強い版である symmetric PIR では、もう 1 つ保証が追加されます。クライアントが学べるのは自分が要求した項目だけであり、データベース内の他のどのエントリについても何も分かりません。これはクライアントだけでなく、データベース自体も保護します。
技術的な読者向けにもう少し詳しく
現代の単一サーバー方式は、格子暗号、最も一般的には learning with errors 仮定の上に構築されています。クライアントの問い合わせは暗号文ベクトルであり、対象インデックスでは 1、それ以外では 0 の暗号化です。そしてこの暗号化は加法準同型であるため、サーバーは復号することなく暗号文同士を足し合わせたり、平文のデータベース項目を掛けたりできます。
サーバーはデータベースを行列として扱い、この暗号化された選択ベクトルを適用し、復号すると目的の行になる単一の暗号文を返します。問い合わせはランダムノイズと見分けがつかないため、サーバーはインデックスについて何の情報も得られません。
歴史的に最大の障害は常にコストでした。素朴に実装すると、サーバーは各問い合わせごとにデータベースの全エントリに触れなければならず、計算コストが高くなります。また暗号文は大きいため、帯域幅のコストも高くなります。近年の研究は、前処理によってこれに対処しています。SimplePIR や FrodoPIR のような方式では、サーバーが事前にデータベースを準備し、各クライアントに小さなヒントを渡せるため、多くの作業をオフライン段階に押し込み、実際の問い合わせを高速にできます。有用な副次的利点として、格子ベースの構成は量子攻撃にも耐性があると考えられており、これは Zcash がより広く進めているポスト量子プライバシーへの移行とも整合します。
Zcash における PIR
PIR は、Zcash をプライベートであると同時に、大規模でも高速に使えるようにする取り組みの一部です。
狙いは、先ほど説明したウォレットスキャンのボトルネックです。Valar Group では、ウォレットがサーバーから自分のデータを取得しても、サーバーにはどのエントリが要求されたのか分からないようにする private information retrieval 技術を開発しています。具体的な応用の 1 つは、nullifier をプライベートに確認することです。nullifier はノートが使用されたときに公開される一意のマーカーで、同じ資金が二重に使われるのを防ぎます。ウォレットはしばしば、特定の nullifier がすでに出現したか、言い換えるとノートがまだ未使用かどうかを確認する必要がありますが、現在これをサーバー経由で行うと、どのノートについて問い合わせているかが漏れる可能性があります。Private information retrieval を使えば、ウォレットはどの nullifier に関心があるのかを明かさずにその質問を行えます。これは、Project Tachyon や新しいノードソフトウェアを含む他のスケーリング作業と並行して進められており、現在プライベートウォレットを制約している性能上の限界を取り除くことを目指しています。
現段階については率直であることが重要です。これは活発な研究とエンジニアリングの最中にあるもので、完成して出荷済みの機能ではありません。概念自体は十分に確立されており、方向性も定まっていますが、日常的なウォレットで普通のデバイス上でも十分効率的に動く PIR を実現することこそ、今まさに取り組まれている難所です。
よくある誤解
- PIR は、どの項目を要求したかを隠しますが、サーバーに接続した事実そのものまで必ずしも隠すわけではありません。ネットワークレベルのメタデータは別の課題です
- PIR は Zcash 固有のものではなく、Zcash がウォレットのプライバシーに適用している一般的な暗号ツールです
- PIR による同期高速化は進行中の目標であり、すでにウォレットに存在する機能ではありません
- 現在の方法である、すべてをダウンロードしてローカルでスキャンするやり方はプライベートですが遅いです。PIR はそのプライバシーを維持したまま遅さを取り除くことを目指しています
関連ページ
