通信高效的私人查找
我有一個場景，客戶端有一個私有集，而伺服器有一個大的公共集，我們想要估計交集大小，或者更具體地說是公共集覆蓋的私有集的百分比。
然而，我們不想通過網路發送整個公共集附近的任何地方，即使是布隆過濾器也會顯得相當大。
伺服器可以發現交集的大小，但不應該對客戶端擁有的特定密鑰有太多了解。
這可能嗎？優先級是按順序最小化通信、客戶端計算、伺服器計算。
以下是一些最近的論文，研究了針對明顯不相等的集合大小的情況優化 PSI。在所有這些論文中，主要目標是減少溝通。
這兩篇論文通過具有高度溝通的離線階段來節省溝通。當需要實際計算交集時，線上交流很少：
- 不平衡的近似私有集相交；阿曼達·克里斯蒂娜·戴維·雷森德、迭戈·F·阿蘭哈
- 移動應用程序中不等集大小的私有集交集；Agnes Kiss、劉健、Thomas Schneider、N. Asokan、Benny Pinkas
本文通過假設伺服器的大集合由兩個（或更多）非共謀方持有來節省通信。這樣，就可以利用私人資訊檢索技術：
- PIR-PSI：擴展私人聯繫人發現；丹尼爾·戴姆勒、彼得·林達爾、邁克·羅蘇萊克、Ni Trieu
您可能會爭辯說，以前的論文是“作弊”，因為它們不在標準的 2 方設置中進行一次性計算。
有幾篇論文在沒有這種“作弊”的情況下實現了低通信，並且這些論文都使用了昂貴的公鑰加密操作（與大集合的大小成正比）。我所知道的最有效的是這個，它使用了某種同態加密：
- 同態加密的快速私有集交集；陳昊、金·萊恩、彼得·林達爾
我碰巧知道這項工作的後續工作將出現在 CCS 2018 上，但尚未線上提供。
您無法避免讓協議“接觸”大集合的每個部分，因此伺服器成本總是會有些高。在 PIR-PSI 中，成本是大集合中每個項目的一些非常便宜的 AES 操作。因此，這是我所知道的最快的（如果您將離線預計算的成本包括在其他工作中）。據我所知，基於 FHE 的方案速度驚人，但比 PIR-PSI 慢一點。
所有這些的最先進技術支持 10-1 億個伺服器項目和 500-5000 個客戶端項目，成本大約為幾秒，通信量可能為 5-20 MB。
我提出了以下解決方案，當數據集的大小差異不大並且我們只想估計交叉點大小時，該解決方案將起作用。我們可以將自己限制為一個隨機子集，因此與其共享完整的公共數據集，不如僅共享一個足夠大的片段，該片段可以以布隆過濾器的形式共享。因此，如果客戶端有 m 條記錄，我們可以請求說一個由雜湊的最後一位定義的 20/m 片段。伺服器將為該片段發送一個布隆過濾器（可能是預先計算的），我們可以再次選擇過濾器中的每個項目 20 位並獲得合理的 FPR。
尚未對估計交叉口大小的預期誤差進行精確的數學計算，但我的餐巾紙背面建議使用 20/m 片段和每個項目 20 位我將在估計交叉口大小時得到 10% 錯誤率的區域。
因此，如果客戶端有 m 個項目，而伺服器有 n>m 個項目，我們可以通過 400*n/m 位傳輸和恆定的非常少的計算得到這樣的估計。
期望伺服器通過請求的片段大小獲得有關客戶端數據集大小的一些資訊，但僅此而已。
我的回答中沒有太多加密，但我認為它會起作用，除非 n 比 m 大得多。