Laconic Private Set-Intersection From Pairings (2022)
Laconic Private Set-Intersection From Pairings (2022)
論文地址：https://eprint.iacr.org/2022/529.pdf
代碼地址：https://github.com/relic-toolkit/relic/tree/main/demo/psi-client-server
代碼運行參考：RELIC 庫學習
Laconic 算法介紹
Laconic 適用于算力和存儲受限的客戶端與算力和存儲能力強大的服務器進行交互的場景。
問題：目前的 PSI 方案需要服務端和客戶端之間進行復雜的計算，這對算力較弱的客戶端很不友好，因為不可能要求其下載并保存巨量的數據，并基于這些數據完成復雜的計算。
2017 年，CDG 等人提出了 Laconic 的概念，Laconic 是一個在具有大輸入的接收方 R（這里指服務端）和具有小輸入的發送方 S（這里指客戶端）之間的交互式協議，協議通常需要滿足下列三個性質：
- 協議應當僅包含兩條消息（也即 Laconic）
- 發送方（客戶端）的總通信開銷與接收方（服務端）的輸入大小無關
- 接收方（服務端）的第一條消息應該可以被多個不同的發送方 \(S_i\)（客戶端）復用，即計算一次，多次使用
本文所提出的兩方 Laconic PSI，滿足上述三個性質，旨在從理論和時間角度最大限度的減少發送方（客戶端）的開銷，發送方（客戶端）的消息大小與其輸入集合呈線性關系，發送方（客戶端）的計算開銷與接收方的輸入無關。
但是，該算法需要在服務端進行大量的計算，服務端的壓力比較大。
PSI Protocol
\(X_{-i}:=X \backslash\left\{x_i\right\}\)：即將 \(x_i\) 從原集合中刪除，剩下的元素組成的新的集合：
協議的具體流程如下：
| 序號 | 階段 | 服務端 Receiver | 客戶端 Sender | |
|---|---|---|---|---|
| 服務端和客戶端共享： 1. \(H:\{0,1\}^* \rightarrow\{0,1\}^\lambda\) 2. \(e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T\) |
||||
| 0 | Setup | \(X=\left\{x_1, \ldots, x_m\right\}\) 獲得 \(\operatorname{setup}_{\mathcal{R}}\) |
可信第三方選擇 \(s \in \mathbb{Z}_q^*\) 1. 計算 \(\operatorname{setup}_{\mathcal{R}}=\left(S_1, S_2, \ldots, S_m\right)\) 傳給服務端：\(S_i=g_2^{s^i} \text { for } i=0, \ldots, m\) 2. 計算 \(\operatorname{setup}_{\mathcal{S}}=\left(S^{\prime}\right)\) 傳給客戶端：\(S^{\prime}=g_1^s\) |
\(Y=\left\{y_1, \ldots, y_n\right\}\) 獲得 \(\operatorname{setup}_{\mathcal{S}}\) |
| 1 | First Round | 將 \(R\) 傳給客戶端 \(\to\) |
獲得 \(R\) | |
| 2 | Second Round | 獲得 \((T_j, U_j)\) | 將 \((T_j, U_j)\) 傳給服務端 \(\leftarrow\) |
計算 \((T_1, U_1, ..., T_n, U_n)\) \(T_j = H\left(e\left(g_1^{t_j}, R\right)\right)\\ U_j = \left(S^{\prime} \cdot g_1^{-y_{\pi(j)}}\right)^{t_j}\) |
| 3 | Retrieve Output | 對每個 \((T_j, U_j)\) 對，計算： For j = 1 to n: For k = 1 to m: 如果 \(H\left(e\left(U_j, R_{-k}\right)\right) \stackrel{?}{=} T_j\)，則表明 \(x_k = y_{\pi(j)}\)， 即 \(x_k\)為交集中元素 |
從上述 Laconic-PSI Protocol 可知：
- 服務端與客戶端僅有兩次交互
- 客戶端的總通信開銷僅與客戶端的輸入大小有關：\((T_j, U_j)\)
- 服務端需要計算一個 R 和 m 個 \(R_{-k}\)，每個值的計算量都非常大（\(R_{-k}=\left(\prod_{i=0}^{m-1} S_i^{p\left(X_{-k}, i\right)}\right)^r=\left(\prod_{i=0}^{m-1} g_2^{{s^i}\times {p\left(X_{-k}, i\right)}}\right)^r\)），這導致服務端的計算耗時比較大，但是可以復用。如果服務端數據保持不變，\(R\) 和所有的 \(R_{-k}\) 首次計算后可以在多個客戶端之間進行復用，但是，一旦服務端數據發生改變（例如增加了新的數據），所有的 \(R\) 都需要重新計算
- 在最后的求交階段（Retrieve Output），每個 $y_j $（或者說 \((T_j, U_j)\)）需要和 m 個 \(R_{-k}\) 進行“比較”，也就是說，為了判斷某個 $y_j $ 是否在交集內，我們最多需要計算 m 次，那么總的計算復雜度為 \(O(mn)\)，這也導致服務端的計算耗時比較大。論文 4.4 中提到了分桶（bucketing）的優化方案，可以將這一步中的計算復雜度由 \(O(mn)\) 降低到 \(O(mn/t)\)，但是該優化方案會增大 First Round 階段服務端的計算和傳輸數據量，具體而言，優化方案的步驟如下：
- 使用哈希函數，將服務端的數據 X 先分裝到 \(t\) 個哈希桶中，這樣每個桶中的數據量為 \(m/t\)
- 使用相同的哈希函數，將客戶端的數據 Y 也分裝到 \(t\) 個哈希桶中，每個桶的數據量為 \(n/t\)
- 然后服務端和客戶端對應的哈希桶獨立地進行上述算法中 First Round 和 Second Round 的計算，即服務端需要對每個桶中的數據獨立計算 R 和 \(m/t\) 個 \(R_{-k}\)，客戶端也對每個桶的數據獨立計算 \((T_j, U_j)\)
- 這樣在 Retrieve Output 階段，需要比較的次數不再是 \(m \times n\)，而是 $t \times m/t \times n/t = mn/t $
證明算法正確性
證明上述算法的正確性：即當 \(H\left(e\left(U_j, R_{-k}\right)\right) \stackrel{?}{=} T_j\) 時，可以證明 \(x_k = y_j\) 為交集中的元素。證明過程如下：
勘誤：服務端需計算 m （非 m-1）個 \(R_{-k}\) 值，k 取值從 1 到 m
與 NR-PSI 比較
服務端的集合大小 \(N_s\) >> 客戶端的集合大小 \(N_c\)
| 兩方交互次數 | 通信開銷 | 客戶端所需容量 | 何方計算交集？ | 計算交集時客戶端的每個元素所需的比較次數 | 服務端計算量 | 當服務端增加新元素 | |
|---|---|---|---|---|---|---|---|
| NR-PSI | 3 + 1 + 2 = 6 | 與服務端的集合大小線性相關 | 較大，需存儲服務端的全部數據（哈希桶） | 客戶端 | 3 + s（布谷鳥哈希） | 較小 | 僅需將新元素加密后插入哈希桶中，然后將新桶發送給客戶端 |
| Laconic PSI | 2 | 與客戶端的集合大小線性相關 | 較小，僅與客戶端集合大小線性相關 | 服務端 | \(N_s\) | 較大 | $$ 與 所有的 \(R_{-k}\) 都需要重新計算，計算量較大 |
NR-PSI 的交互次數計算如下：參考 隱私求交代碼實踐
- Base Phase：R-OT 需要兩方進行 3 次交互
- 服務端 \(\to\) 客戶端：\((h_0, h_1)\)
- 服務端 \(\leftarrow\) 客戶端：\((v_0, v_1)\) 和 \(u\)，OT 階段結束
- 服務端 \(\leftarrow\) 客戶端：\(u^i = G(k_{i,0})\bigoplus G(k_{i,1})\bigoplus r\)，R-OT 結束
- Setup Phase：1 次，傳輸 CF
- 服務端 \(\to\) 客戶端：Cuckoo Filter (CF)
- Online Phase：2 次
- 服務端 \(\leftarrow\) 客戶端：\(b_{i,j} = c_{i,j} \bigoplus y_i[j]\)
- 服務端 \(\to\) 客戶端：\(r_{i, j}^{1-b_{i, j}} \oplus\left(r_{i, j}^{b_{i, j}} \cdot a_j\right)\) 和 \(\tilde{g}\)
浙公網安備 33010602011771號