Loading article…
暗号化において、プライベート情報検索 (PIR)プロトコルは、データベースを所有するサーバーから、どの項目が取得されるかを明かさずに項目を取得できるようにするプロトコルです。PIR は 1-out-of -n 忘却転送の弱いバージョンであり、ユーザーが他のデータベース項目に関する情報を取得してはならないことも要求されます。
PIR を実現する単純だが非常に非効率的な方法の 1 つは、サーバーがデータベースのコピー全体をユーザーに送信することです。実際、これは単一サーバー設定でユーザーのクエリに対して情報理論的プライバシーを提供する唯一の可能なプロトコルです (古典的または量子設定[1] )。 [2]この問題に対処するには 2 つの方法があります。サーバーを計算的に制限するか、それぞれがデータベースのコピーを持つ複数の非協力的なサーバーがあると想定します。
この問題は、1995年にChor、Goldreich、Kushilevitz、Sudan [2]によって情報理論の設定で導入され、1997年にKushilevitzとOstrovskyによって計算の設定で導入されました。 [3]それ以来、非常に効率的な解決策が発見されました。単一データベース（計算上プライベート）PIRは、一定の（償却された）通信で実現でき、kデータベース（情報理論的）PIRは通信で実行できます。
計算PIRの進歩
未満の通信複雑度を実現する最初の単一データベース計算 PIR 方式は、1997 年に Kushilevitz と Ostrovsky [3]によって作成され、任意の に対しての通信複雑度を実現しました。ここで はデータベース内のビット数です。彼らの方式のセキュリティは、よく研究されている二次残余問題に基づいています。1999 年に、Christian Cachin、Silvio Micali、Markus Stadler [4]は、多重対数通信複雑度 を実現しました。彼らのシステムのセキュリティは、ファイ隠蔽仮定に基づいています。2004 年に、Helger Lipmaa [5] は、対数二乗通信複雑度 を実現しました。ここで は文字列の長さ、 はセキュリティ パラメータです。彼のシステムのセキュリティは、Damgård–Jurik 暗号システムのような長さに柔軟な加法準同型暗号システムの意味的セキュリティにまで低下します。 2005年にクレイグ・ジェントリーとズルフィカール・ラムザン[6]は、データベースの対数二乗（連続）ビットを取得する対数二乗通信複雑性を達成した。彼らの方式のセキュリティも、ファイ隠蔽仮定の変形に基づいている。通信速度は、 2015年にアゲロス・キアイアス、ニコス・レオナルド、ヘルガー・リップマー、カテリーナ・パヴリク、チャン・タンによって最終的に まで削減された。 [7]
これまでのすべての非線形通信計算PIRプロトコルは、公開鍵操作の線形計算量を必要としました。2009年に、Helger Lipmaa [8]は、通信の複雑さと公開鍵操作の最悪ケースの計算を備えた計算PIRプロトコルを設計しました。連続しないビットを取得する償却技術は、Yuval Ishai、Eyal Kushilevitz、 Rafail Ostrovsky、Amit Sahaiによって検討されました。[9]
OstrovskyとSkeith [10]が示したように、KushilevitzとOstrovsky [3]とLipmaa [5]の方式は準同型暗号化に基づく同様のアイデアを使用しています。KushilevitzとOstrovskyのプロトコルはGoldwasser-Micali暗号システムに基づいており、LipmaaのプロトコルはDamgård-Jurik暗号システムに基づいています。
情報理論的PIRの進歩
情報理論的セキュリティを実現するには、複数の非協力的なサーバーがあり、それぞれがデータベースのコピーを持っているという仮定が必要です。この仮定がなければ、情報理論的に安全な PIR プロトコルは、少なくともデータベースのサイズnの通信量を必要とします。応答しないサーバーや悪意のある/共謀しているサーバーを許容するマルチサーバー PIR プロトコルは、それぞれ堅牢またはビザンチン堅牢と呼ばれます。これらの問題は、Beimel と Stahl (2002) によって最初に検討されました。k 個のサーバーのみが応答し、ν 個のサーバーが誤って応答し、クライアントのクエリを明らかにすることなく最大t 個の共謀サーバーに耐えることができる ℓ サーバー システムは、「 tプライベート ν ビザンチン堅牢k ℓ 外 PIR」と呼ばれます[DGH 2012]。 2012年、C. Devet、I. Goldberg、N. Heninger (DGH 2012)は、理論上の最大値であるビザンチン堅牢性を備えた最適堅牢性スキームを提案しました。これは、シャミアの秘密分散を使用してクエリを隠す、Goldbergの以前のプロトコルに基づいています。Goldbergは、 SourceForgeでC++実装をリリースしました。[11]
他の暗号プリミティブとの関係
一方向関数は、非自明な（すなわち、線形通信でない）単一データベースの計算上プライベートな情報検索に必要ですが、十分であるかどうかはわかっていません。実際、そのようなプロトコルは、ジョバンニ・ディ・クレセンツォ、タル・マルキン、ラファエル・オストロフスキーによって、忘却転送を意味することが証明されました（以下を参照）。[12]
忘却転送は対称 PIR とも呼ばれ、ユーザーが要求した項目以外の項目を学習できないという追加の制限が課された PIR です。ユーザーとデータベースの両方にプライバシー要件があるため、対称と呼ばれます。
衝突耐性のある暗号ハッシュ関数は、 Ishai、Kushilevitz、Ostrovskyによって示されているように、1ラウンドの計算PIRスキームによって暗黙的に想定されます。[13]
PIRのバリエーション
プライベート情報検索の基本的な動機は、当事者の一方 (送信者) がデータベースを所有し、もう一方 (受信者) が特定のプライバシー制限と保証付きでデータベースを照会したいという、2 者間プロトコルのファミリーです。したがって、プロトコルの結果として、受信者がデータベースのi 番目の値が必要な場合、受信者はi 番目のエントリを知る必要がありますが、送信者はiについて何も知る必要はありません。一般的な PIR プロトコルでは、計算上無制限の送信者はiについて何も知ることができないため、プライバシーは理論的に保護されます。PIR 問題が提起されて以来、その解決に向けてさまざまなアプローチが追求され、いくつかのバリエーションが提案されています。
CPIR（計算上秘密情報検索）プロトコルはPIRプロトコルに似ています。受信者は送信者のデータベースから選択した要素を取得しますが、送信者はどの要素が転送されたかについての知識を取得しません。[8]唯一の違いは、多項式的に制限された送信者に対してプライバシーが保護されることです。[14]
CSPIR（計算対称型秘密情報検索）プロトコルは、CPIRプロトコルが使用される同様のシナリオで使用されます。送信者がデータベースを所有しており、受信者がこのデータベースのi番目の値を取得したい場合、SPIRプロトコルの実行終了時に、受信者はデータベース内のi番目以外の値について何も知らないはずです。[14]
PIR実装
文献には数多くの計算 PIR および情報理論的 PIR スキームが実装されています。以下は不完全なリストです。
- MuchPIR [15]は、 Postgres C/C++拡張機能としてのCPIR実装です[GitHub、2021]。
- SealPIR [16]は高速CPIR実装である[ACLS 2018]。
- Popcorn [17]はメディア向けにカスタマイズされたPIR実装である[GCMSAW 2016]。
- Percy++ [11]には[AG 2007、DGH 2012、CGKS 1998、Goldberg 2007、HOG 2011、LG 2015]の実装が含まれています。
- RAID-PIR [18]は[DHS 2014]のITPIRスキームの実装である。
- XPIR [19]は高速CPIR実装である[ABFK 2014]。
- upPIR [20]はITPIRの実装である[Cappos 2013]。
注記
- ^ Baumeler, Ämin; Broadbent, Anne (2014 年 4 月 17 日). 「量子秘密情報検索には線形通信複雑性がある」. Journal of Cryptology . 28 : 161–175. arXiv : 1304.5490 . doi :10.1007/s00145-014-9180-2. S2CID 1450526.
- ^ ab チョー、ベニー;クシレヴィッツ、エール。ゴルドライヒ、オーデッド。スーダン、マドゥ（1998年11月1日）。 「個人情報の検索」（PDF）。ACM のジャーナル。45 (6): 965–981。CiteSeerX 10.1.1.51.3663。土井：10.1145/293347.293350。S2CID 544823。
- ^ abc Kushilevitz, Eyal; Ostrovsky, Rafail (1997). 「レプリケーションは不要: 単一データベース、計算上プライベートな情報検索」。第 38 回コンピュータサイエンスの基礎に関する年次シンポジウムの議事録。米国フロリダ州マイアミビーチ: IEEE コンピュータ協会。pp . 364–373。CiteSeerX 10.1.1.56.2667。doi : 10.1109 / SFCS.1997.646125。ISBN 978-0-8186-8197-4.S2CID 11000506 。
- ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). 「多対数通信による計算上プライベートな情報検索」。Advances in Cryptology – EUROCRYPT '99 。プラハ、チェコ共和国: Springer - Verlag。pp. 402–414。doi :10.1007/3-540-48910- X_28。ISBN 978-3-540-48910-8。
- ^ ab Lipmaa, Helger (2005). 「対数二乗通信による無記名転送プロトコル」。第 8 回国際情報セキュリティ会議( ISC 2005) の議事録。コンピュータサイエンスの講義ノート。第 3650 巻。シンガポール: Springer-Verlag。pp. 314–328。CiteSeerX 10.1.1.73.8768。doi : 10.1007 / 11556992_23。ISBN 978-3-540-31930-6。
- ^ Gentry, Craig; Ramzan, Zulfikar (2005). 「一定通信速度での単一データベースのプライベート情報検索」. ICALP . LNCS. Vol. 3580. Springer. pp. 803–815. CiteSeerX 10.1.1.113.6572 . doi :10.1007/11523468_65.
- ^ Kiayias, Aggelos; Leonardos, Nikos; Lipmaa, Helger; Pavlyk, Kateryna; Tang, Qiang (2015). 「準同型暗号化からの最適レート個人情報取得」。プライバシー強化技術に関する議事録 2015。 Vol. 2015. DE GRUYTER。 pp. 222–243。doi : 10.1515/popets-2015-0016。hdl : 20.500.11820/0f84afcb-8ee1-4744-a2ba-4642104c51c5。
- ^ ab Lipmaa, Helger (2010). 「データ依存計算による最初の CPIR プロトコル」。情報セキュリティと暗号に関する第 12 回国際会議の議事録。コンピュータサイエンスの講義ノート。第 5984 巻。ソウル、韓国: Springer-Verlag。pp. 193–210。CiteSeerX 10.1.1.215.7768。doi : 10.1007 / 978-3-642-14423-3_14。ISBN 978-3-642-14423-3。
- ^ イシャイ、ユヴァル;クシレヴィッツ、エール。オストロフスキー、ラファイル。サハイ、アミット (2004)。 「バッチコードとその応用」(PDF)。STOC'04。 ACM。 262–271ページ。土井：10.1145/1007352.1007396 。2015 年 10 月 23 日に取得。
- ^ Ostrovsky, Rafail; Skeith III; William E. (2007). 「単一データベースのプライベート情報検索の調査: テクニックとアプリケーション」。公開鍵暗号の実践と理論に関する第 10 回国際会議の議事録。Springer-Verlag。pp. 393–411。doi : 10.1007 / 978-3-540-71677-8_26。ISBN 978-3-540-71677-8。
- ^ ab Percy++ / SourceForgeの C++ での PIR
- ^ Di Crescenzo, Giovanni; Malkin, Tal; Ostrovsky, Rafail (2000)。「単一データベースのプライベート情報検索は、無意識の転送を意味する」。Eurocrypt 2000 . LNCS. Vol. 1807. Springer. pp. 122–138. doi : 10.1007/3-540-45539-6_10。
- ^ イシャイ、ユヴァル;クシレヴィッツ、エール。オストロフスキー、ラファイル（2005）。 「耐衝突性ハッシュの十分条件」。第 2 回暗号理論会議の議事録。米国マサチューセッツ州ケンブリッジ: Springer-Verlag。 445–456ページ。土井：10.1007/978-3-540-30576-7_24。ISBN 978-3-540-30576-7。
- ^ ab Saint-Jean, Felipe (2005). 「単一データベースの計算対称プライベート情報検索 (cSPIR) プロトコルの Java 実装」(PDF)。イェール大学技術レポート YALEU/DCS/TR-1333。
- ^ 「MuchPIR デモ」。GitHub。2021年9月14日。
- ^ 「SealPIR」。Github 。 2018年6月7日閲覧。
- ^ 「ポップコーン」(PDF) 。 2016年8月21日時点のオリジナル(PDF)よりアーカイブ。 2016年5月26日閲覧。
- ^ "encryptogroup/RAID-PIR". GitHub . 2016年5月26日閲覧。
- ^ 「XPIR-team/XPIR」。GitHub 。 2016年5月26日閲覧。
- ^ "upPIR". uppir.poly.edu . 2016年6月25日時点のオリジナルよりアーカイブ。2016年5月26日閲覧。
参照
参考文献
- A. Beimel、Y. Ishai、E. Kushilevitz、J.-F. Raymond。情報理論的プライベート情報検索の障壁を打破。第 43 回 IEEE コンピュータ サイエンスの基礎に関するシンポジウムの議事録、カナダ、バンクーバー、2002 年、261 ～ 270 ページ。
- A. Beimel と Y. Stahl、「堅牢な情報理論的プライベート情報検索」、第 3 回国際通信ネットワーク セキュリティ会議 (SCN'02) の議事録、326 ～ 341 ページ、2003 年。引用元は DGH 2012、op. cit です。
- [DGH 2012] Casey Devet、Ian Goldberg、Nadia Heninger、「最適に堅牢な個人情報検索」、第 21 回 USENIX セキュリティ シンポジウム、2012 年 8 月。
- [AG 2007] C. Aguilar-Melchor および P. Gaborit。格子ベースの計算効率の高いプライベート情報検索プロトコル、Western European Workshop on Research in Cryptology (WEWoRC)、2007 年。
- [CGKS 1998] B. Chor、O. Goldreich、E. Kushilevitz、および M. Sudan、「個人情報の検索」、Journal of the ACM、45(6):965–981、1998。
- [ゴールドバーグ 2007] I. ゴールドバーグ、「プライベート情報検索の堅牢性の向上」、IEEE セキュリティとプライバシーに関するシンポジウム (S&P)、2007 年。
- [HOG 2011] R. Henry、F. Olumofin、I. Goldberg、「電子商取引のための実用的なPIR」、ACM コンピュータおよび通信セキュリティ会議 (CCS)、2011 年。
- [LG 2015] W. Lueks および I. Goldberg、「マルチクライアントのプライベート情報検索のためのサブ線形スケーリング」、国際金融暗号化およびデータセキュリティ会議 (FC)、2015 年。
- [DHS 2014] D. Demmler、A. Herzberg、T. Schneider、「RAID-PIR: 実用的なマルチサーバー PIR」、クラウド コンピューティング セキュリティ ワークショップ (CCSW)、2014 年。
- [ABFK 2014] C. Aguilar-Melchor、J. Barrier、L. Fousse、および M.-O. Killijian、「XPIR: すべての人のための個人情報検索」、Cryptology ePrint Archive、レポート 2014/1025、2014 年。
- [GCMSAW 2016] T. Gupta、N. Crooks、W. Mulhern、S. Setty、L. Alvisi、およびM. Walfish、 [1] Popcornによるスケーラブルでプライベートなメディア消費。USENIX NSDI、2016年3月。
- [Cappos 2013] J. Cappos、「理論的最適性の回避によるセキュリティ更新の効率的かつプライベートな取得」、金融暗号化およびデータセキュリティに関する国際会議 (FC)、2013 年。
- Sergey Yekhanin. 新しいローカルでデコード可能なコードとプライベート情報検索スキーム、ECCC TR06-127、2006 年。
- [ACLS 2018] S. Angel、H. Chen、K. Laine、S. Setty、「圧縮クエリと償却クエリ処理を備えた PIR」、IEEE セキュリティとプライバシーに関するシンポジウム (S&P)、2018 年。
外部リンク
- ヘルガー・リップマーの忘却転送と PIR に関する Web リンク
- 調査記事を含むPIRに関するウィリアム・ガサーチのウェブサイト
- PIRの記事と調査が掲載されているラファエル・オストロフスキーのウェブサイト