秘匿情報検索（PIR）

解きたい問題：クエリの「中身」ではなく「どれを引いたか」を隠す

データの秘匿というと暗号化を思い浮かべますが、PIR が守るのはまったく別の情報です。あなたが特許 DB・遺伝子 DB・株価 DB を検索するとき、どの項目を引いたかそれ自体が秘密になり得ます。「この会社の特許を調べた」「この遺伝子変異を照会した」という事実は、たとえ回答内容を暗号化しても、サーバーが「何番の項目が要求されたか」を見れば筒抜けです。

通信を TLS で暗号化しても解決しません。TLS はクライアントとサーバー間の第三者に対して中身を隠すだけで、サーバー自身はどのインデックス i が要求されたかを平文で受け取ります。サーバーを信頼できない（あるいはログ・召喚・侵害を恐れる）状況では、サーバーに対してクエリを隠す必要があります。これが PIR（Private Information Retrieval、秘匿情報検索） の課題です。

素朴な解は一つだけあります。DB 全体をダウンロードして手元で i 番目を引くことです。サーバーは何も学びませんが、N 項目すべてを送るため通信量が O(N) になり、大規模 DB では非現実的です。PIR の研究は「サーバーにインデックスを漏らさず、かつ DB 全体を送るより安く済ませる」ことを目指します。

安全性の定義：クエリの分布が i に依存しないこと

PIR の安全性は明快に定義できます。クライアントが引きたいインデックスを i とし、サーバーへ送るクエリを q(i) とします。

• 情報理論型（information-theoretic PIR）：任意の二つのインデックス i と j に対し、サーバーが受け取るクエリの分布が完全に同一である。つまり q(i) と q(j) は分布として区別不能で、計算能力が無限のサーバーでも i を特定できない。
• 計算量型（computational PIR, cPIR）：q(i) と q(j) が計算量的に区別不能である。多項式時間のサーバーには見分けられないが、無限の計算能力があれば原理的には区別され得る。暗号の困難性仮定に依存する。

安全性のイメージ（1 サーバーで見える情報）:
  i=3 を引くとき送るクエリ  q(3)
  i=7 を引くとき送るクエリ  q(7)
    情報理論型 : 分布が完全一致 → 情報量ゼロで i は不明
    計算量型   : 多項式時間では q(3) と q(7) を判別不能

ここで重要なのは、PIR は原則として回答の正しさ（i 番目を確かに得られる）とインデックスの秘匿を両立させる点で、回答の中身をサーバーから隠すことは必ずしも要求しない（DB が公開データなら中身の秘匿は不要なことも多い）。中身も隠したい場合は 検索可能暗号 など別の道具と組み合わせます。

情報理論型 PIR：複数サーバーへの複製と XOR 合成

Chor・Goldreich・Kushilevitz・Sudan（1995）が示した古典的な多サーバー PIR は、驚くほど単純です。DB を k 台のサーバーに同一複製し、サーバー同士は**結託しない（non-colluding）**と仮定します。DB を N ビットの列 x[1..N] と見ます。2 サーバーの最も基本的な構成はこうです。

2 サーバー IT-PIR（i 番目のビット x[i] を私的に取得）:
  1. クライアントは長さ N の乱数ビット列 S1 を一様ランダムに選ぶ
  2. S2 = S1 の i 番目だけを反転したもの（S2 = S1 XOR e_i）
        e_i は i 番目だけ 1 のベクトル
  3. サーバー1 へ S1 を、サーバー2 へ S2 を送る
  4. 各サーバーは「自分のクエリで 1 が立つ添字の x を全部 XOR」した 1 ビットを返す
        a1 = XOR over {j : S1[j]=1} of x[j]
        a2 = XOR over {j : S2[j]=1} of x[j]
  5. クライアントは a1 XOR a2 を計算 → これが x[i]

なぜ正しいか。a1 XOR a2 を展開すると、S1 と S2 で立っているビットが異なる添字だけが生き残ります。両者は i 番目でしか違わないので、a1 XOR a2 = x[i] になります。なぜ隠れるか。各サーバーが受け取るのは一様ランダムなビット列（S1 は定義から一様、S2 = S1 XOR e_i も一様）で、単体では i の情報をまったく含みません。二つを突き合わせれば e_i が復元されて i が割れますが、それはサーバーが結託した場合だけです。

素朴には各サーバーが N ビットのクエリを受け取り 1 ビット返すので通信は O(N) ですが、DB を多次元の格子（キューブ）に並べ替えて次元ごとに問い合わせることで、サーバー数 k を増やすほど通信量をサブ線形（例：O(N の 1/k 乗) 級）に下げられます。非結託という仮定の対価として、単一サーバーでは不可能な情報理論的安全が手に入るのが多サーバー型の価値です。この「複製した DB へ、単体では秘密を漏らさない乱択クエリを配る」構図は Shamir 秘密分散と閾値暗号 の発想と地続きで、より高次の PIR は秘密分散を明示的に用います。

計算量型 PIR（cPIR）：準同型暗号で単一サーバーを実現する

複製も非結託仮定も置きたくない――つまりサーバー 1 台で済ませたい場合は、計算量的仮定に切り替えます。Kushilevitz・Ostrovsky（1997）が最初の単一サーバー cPIR を示し、鍵となるのが加法準同型暗号です。加法準同型とは、平文を復号せずに暗号文同士で「平文の足し算」に相当する演算ができる性質で、詳しくは 準同型暗号と秘密計算（MPC） を参照してください。

最も基本的なアイデア（選択ベクトル方式）はこうです。DB を長さ N のベクトル x[1..N] とし、クライアントは選択ベクトル b を暗号化して送ります。b は i 番目だけが 1、他は 0 のベクトルで、各成分を暗号化した Enc(b[1]), …, Enc(b[N]) を送ります。準同型性により、サーバーは復号せずに次を計算できます。

単一サーバー cPIR（選択ベクトル方式の骨子）:
  クライアント: b[j] = 1 (j=i のとき), 0 (それ以外)
               各 b[j] を暗号化して Enc(b[1]) .. Enc(b[N]) を送信
  サーバー   : 答え = Σ_j  Enc(b[j]) を x[j] 倍したもの
               （加法準同型で「暗号文の重み付き和」を平文を見ずに計算）
             = Enc( Σ_j b[j]*x[j] ) = Enc( x[i] )   ← i 番目だけ生き残る
  クライアント: 受け取った暗号文を復号 → x[i]

サーバーは各暗号文が 0 の暗号化か 1 の暗号化かを判別できません（意味論的安全性）。よってどの位置が選ばれたか＝ i を学べません。ここでのコストは明確です。サーバーは DB の全項目 x[1..N] に準同型演算を施す必要があり、サーバー計算は必ず O(N) かかります（i 番目だけ触れば、触った位置から i が漏れてしまうため、全走査は原理的に避けられない）。一方、送受信するのは選択ベクトルと 1 個の答えなので通信量は小さくできます。

通信量・計算量・信頼のトレードオフ

PIR の設計は、三つの資源――通信量・サーバー計算量・信頼仮定――のトレードオフに集約されます。

• 通信量 vs 計算量：cPIR は通信を極小にできる代わり、サーバーが DB 全体に重い準同型演算をかけるため CPU コストが高い。素朴解（DB 全ダウンロード）は逆に計算ゼロだが通信 O(N)。多くの実用系はこの両端の間で「サーバー計算 O(N) は許容し、通信をサブ線形に抑える」点を狙います。
• 信頼仮定 vs 実現可能性：情報理論型は無条件安全という強さを持つが、複数サーバーと非結託という運用上重い仮定を要する（1 台でも全台と結託・侵害されれば破れる）。cPIR は 1 台で済むが、格子問題などの困難性に安全が依存する。
• オフライン前処理：近年の実用 PIR（例：SimplePIR/DoublePIR 系や preprocessing PIR）は、DB 依存の重い計算を一度だけオフラインで前処理し、オンラインのクエリごとの計算・通信を大幅に削る。前処理をクライアント側にヒントとして持たせることで、オンラインのサーバー計算を O(N) からサブ線形に落とす方向が主流になりつつあります。

インデックス PIR からキーワード PIR・PIR-with-preprocessing へ

ここまでは「i 番目を引く」インデックス PIR でしたが、実務では「このキーワードに一致する項目」を引きたい。これを キーワード PIR と呼び、インデックス PIR の上に構築します。典型的には、クライアントが手元でキーワードのハッシュから DB 内の位置を特定し（あるいは PIR で索引構造を私的に辿り）、その位置へインデックス PIR を適用します。パスワード漏洩チェック（自分のパスワードを送らず「漏洩済みか」を照会する）や、証明書失効の私的確認、私的な DNS 参照などが応用例です。

まとめ

PIR（秘匿情報検索） は、DB の i 番目を取り出しつつどの i を引いたかをサーバーに漏らさない技術です。守るのはデータの中身ではなくクエリのインデックスであり、TLS のような通信暗号化ではサーバー自身に i が見えてしまうため、専用の構成が要ります。素朴には DB 全体を送れば隠せますが O(N) の通信がかかり、それを下回る道は二つ――非結託の複数サーバーへ複製して乱択クエリを XOR 合成する情報理論型（無条件安全だが運用仮定が重い）か、加法準同型暗号で単一サーバーを実現する計算量型 cPIR（1 台で済むが困難性仮定に依存し、サーバー計算が O(N) と重い）か、です。単一サーバーで情報理論的秘匿を得るには O(N) の送信が原理的に避けられないという下界が、この分岐を生みます。設計の本質は通信量・サーバー計算量・信頼仮定のトレードオフで、DB を行列に畳んで通信を O(√N) に、前処理でオンライン計算をサブ線形に落とすのが実用化の鍵です。「どこを読んだか」を隠す 忘却 RAM（ORAM）、「暗号化したまま計算する」 準同型暗号と秘密計算（MPC） と併せて、データを使いながら漏らさない技術群として押さえると全体像が描けます。