打開鏈接點亮社區Star，照亮技術的前進之路。每一個點贊，都是社區技術大佬前進的動力。
Github 地址： https://github.com/secretflow/secretflow
1. The Problem of Private Information Retrival
PIR 全稱為 Private Information Retrival，直觀的翻譯名字為“私有信息檢索”。
已知的最早提出 PIR 的文章是 1995 年 Benny Chor, et. al. [1]。在文章最開始的時候，提到了在傳統的 query 場景中，我們有一個 client 發送 query，有 server 回覆結果。
從抽象角度來看，我們可以試圖保護：
- Server 數據的安全性
- Client query 的安全性
在 [1] 之前，有許多工作在研究如何保護 server 端 DB 數據的安全性，在此不再贅述
。Benny Chor, et. al. [1] 提出了一個問題：我們是否可以在 query 場景中保護 client query 的隱私性？由於當時分佈式數據庫存儲的發展，因此他們提出了一個基於 replicated DB (and non-colluding) 的方案。
這就是 PIR 的場景性問題，根據現實中不同的 client 以及 server 的假設，我們可以把協議進行分類。
2. PIR 場景的分類
我們可以看到，PIR 場景中的實體有 client 以及 server，並且 client 向 server 發送了一個需要保護隱私的 query ，server 向 client 返回一個 query 的最終結果。
如果我們僅僅需要保護 query 的隱私、而又不在意性能 ，是有一個很簡單的解決方案。
我們可以讓 server 將其持有的所有數據全量發送給 client，由 client 本地進行搜索查詢並得到結果。
顯然，這種方案是十分低效的。我們尋求一種協議可以比這種簡單的解決方案更加高效。
2.1 單server場景(單個數據庫)&多server場景(分佈式數據庫)
如果我們假設 DB 只有一個，那麼場景就是如下圖所示：
這種情況下我們一般採取加密查詢數據，之後交給 server 去作查詢/匹配操作以得到正確的查詢結果。
例如基於任意加法同態算法的 [1]，全同態加密的 SealPIR [2]，以及返回一個 block 的查詢結果的 [3]。
PIR 的研究者們同樣證明了：在單 DB 的場景中，所有的 PIR 協議必須基於某個數學難題（這類 PIR 協議也叫做 computational PIR (cPIR) 協議），我們不可能構造出一個單 DB PIR 協議滿足 unconditional security
如果我們假設有許多個 replicated DB，那麼場景就是如下圖所示：
這種情況下我們可以達到 unconditional security，例如基於 DPF 的 PIR [4] 等等。
但是多 server 場景中有兩條關鍵假設：
- 數據庫是 replicated，因此每個數據庫都持有相同的數據集
- 數據庫中存在 non-colluding 的假設，server 之間存在不可共謀的假設（例如 honest majority or only one honest server）
2.2 保護數據庫隱私 (Symmetric PIR, sPIR)
如果我們試圖保護：
（1）DB 數據的安全性；
（2）Client query 的安全性;
那麼我們叫這種協議為 symmetric PIR。我們之前提到的一些算法，例如基於任意加法同態算法的 [1] 以及全同態加密的 SealPIR [2] 都同時保護了數據庫的隱私，因此也屬於 sPIR。
2.3 基於索引查詢/基於匹配查詢
- 基於索引：index PIR
- 基於查詢：keyword PIR
基於索引/匹配的 PIR 協議在單 DB 和多 DB 的情況下均成立，我們下面以單 DB 的方案為例。
基於索引的 PIR
基於索引的 PIR 要求 client 在查詢數據庫之前，已經預先得知想要查詢的數據索引信息。
如果我們有一個原本是 (key, value) 的 DB 的話，那麼其實並不一定必須要使用基於匹配的 PIR。
- 如果 DB 中的 key 屬於非隱私信息，那麼我們可以使用一個
encoding函數，將每個數據庫元素的 key 映射到某個 index 上，然後對數據庫進行重新排序，那麼在 client 想要插敍某個 key 的時候，可以直接使用公開的encoding函數獲取到 key 相對應的 index 值。 - 但是如果 DB 中的 key 屬於隱私信息，那麼也就意味着我們必須使用 sPIR 來保護數據庫隱私，而 DB 使用的 encoding 函數本身可能會泄漏數據庫 key 的分佈情況，因此在這種情況下我們只能使用基於匹配的 PIR。
基於匹配的 PIR
基於匹配的 PIR 實際上和 PSI with Payload 很相似。場景如下圖所示：
其實就是 one-element PSI with Payload。PSI with Payload 使用 client 的輸入 ki 以及 DB 的輸入 {k1,..., kn} 進行撞庫，把匹配後數據（也就是 ki）的 value 返回給 client。
其中保護了
- client 不知道未匹配到的 key 是什麼
- client 不知道未匹配到的 key 的 value 是什麼
- DB 不知道具體匹配結果的 key 是什麼（有些 PSI 算法可以額外保證這些）
- DB 不知道具體匹配結果的 value 是什麼（有些 PSI 算法可以額外保證這些）
相關資料
【課程】https://cyber.biu.ac.il/event/the-12th-biu-winter-school-on-c...
【代碼】https://github.com/microsoft/SealPIR
【代碼】https://github.com/OpenMined/PIR參考文獻
[1] Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan. "Private Information Retrieval". FOCS (1995).
[2] Angel, Sebastian G. et al. “PIR with Compressed Queries and Amortized Query Processing.” 2018 IEEE Symposium on Security and Privacy (SP) (2018): 962-979.
[3] Gentry, Craig and Zulfikar Ramzan. “Single-Database Private Information Retrieval with Constant Communication Rate.” ICALP (2005).
[4] Gilboa, Niv and Yuval Ishai. “Distributed Point Functions and Their Applications.” EUROCRYPT (2014).
本文由隱語社區統一發布，歡迎大家點 Star
