沉默的不經意轉移問題
最近，博伊爾等。人。建議靜默 OT 擴展。在論文中，沉默的 OT似乎將基於 GGM 的 PPRF 用作建構塊。但是，讀完論文後，我有兩個不清楚的問題：
- 為了 $ t $ -points PPRF，作者建議有 $ t $ 建構獨立的單點 PPRF，這樣這些單點 PPRF 可以加在一起形成一個多點 PPRF。與要求接收器輸入選擇位向量（即 PPRF 中的點）的相關 OT（IKNP 樣式）相比，這是否意味著我想要 $ t $ 1 在 COT 選擇位向量中，我需要設置 $ t $ 多點PPRF中的對應點？
- 即使將這個多點 PPRF 與仍然要求接收器輸入選擇位向量的隨機 OT 進行比較，是否無論如何都可以將這個隨機選擇位轉換為選擇位，而幾乎沒有或沒有額外的通信成本？
感謝您的任何建議和幫助。
- 不，因為這只是一個中間步驟。粗略地說，如果你想得到 $ n $ 標準（相關或不相關）OT，接收者選擇他得到的東西，我們的建構有四個主要步驟：
a) 建立一個相關的 OT，其中選擇向量是隨機的 $ t $ -稀疏向量（一個非常大的向量，但只有 $ t $ 隨機 1）。這是使用總和完成的 $ t $ PPRF。
b) 將“具有稀疏選擇向量的相關 OT”轉換為“具有偽隨機選擇向量的相關 OT”。這是使用雙 LPN 假設完成的。這裡的想法很簡單：在做（a）之後，發送者有 $ \Delta, \vec q_0 $ , 並且接收者有 $ \vec b, \vec q_1 $ ， 在哪裡 $ \vec q_0 + \vec q_1 = \Delta\cdot \vec b $ , 其中向量的長度 $ n $ 和 $ \vec b $ 是 $ t $ -sparse（這正是 $ n $ 將 OT 與 $ t $ -選擇位的稀疏向量）。現在，各方使用公共隨機壓縮矩陣將他們的向量相乘 $ H $ : 發件人有 $ (\Delta, H\cdot \vec q_0) $ 並且接收器有 $ (H\cdot \vec b, H\cdot \vec q_1) $ . 請注意
$ H\cdot \vec q_0 + H\cdot \vec q_1 = H\cdot (\vec q_0+\vec q_1) = H\cdot (\Delta\cdot \vec b) = \Delta\cdot (H\cdot \vec b) $ ,
所以這仍然是 $ n $ 相關的 OT，但現在選擇位的向量是 $ H\cdot \vec b $ . 根據雙 LPN 假設，如果 $ \vec b $ 是隨機的 $ t $ -稀疏向量，然後這個 $ H\cdot \vec b $ 與真正的隨機向量無法區分。
c) 如果您最終想要不相關的 OT，請將 $ n $ 將具有上述偽隨機選擇位的 OT 關聯到 $ n $ 具有隨機選擇位的標準 OT；這使用了 IKNP 風格的去相關，即，只需使用相關性強的散列函式對所有內容進行散列，以“破壞”相關性。如果您對相關 OT 沒有問題，請跳過此步驟。
d) 只剩下轉換你的 $ n $ 具有偽隨機選擇位的 OT 轉換為具有選擇位的 OT。這實際上是您的問題2：
- 有一種標準方法可以將具有隨機選擇位（以及隨機輸入）的 OT 轉換為具有選擇輸入和選擇位的標準 OT。這涉及每個 OT 的三位通信，這是最佳的（您不能希望使用選擇的“選擇位”，使用少於三位的通信從兩個選擇的位中傳輸一位）。請注意，靜默 OT 在生成的 OT 總數中具有次線性通信，但僅因為輸入和選擇位是偽隨機的 - 轉換為標準 OT，它們為 OT 提供了準最優通信， $ 3+o(1) $ 每 OT 位（攤銷 $ n $ 實例）。
標準方法比較簡單。發件人有隨機輸入 $ (r_0,r_1) $ 和真正的輸入 $ (s_0,s_1) $ . 接收器有隨機選擇位 $ b $ ， 知道 $ r_b $ （因為隨機OT），並且有真正的選擇位 $ \sigma $ . 然後，接收器執行以下操作（ $ \oplus $ 表示異或）：
- 如果 $ b = \sigma $ , 要求接收方發送 $ (u_0, u_1) = (r_0 \oplus s_0, r_1 \oplus s_1) $ , 並恢復 $ s_\sigma = s_b = u_b \oplus r_b $ .
- 如果 $ b \neq \sigma $ , 要求接收方發送 $ (u_0, u_1) = (r_0 \oplus s_1, r_1 \oplus s_0) $ , 並恢復 $ s_\sigma = s_b = u_{1-b} \oplus r_b $ .
請注意，從接收方到發送方的消息僅涉及通信 $ b \oplus \sigma $ ，即告訴發件人如果 $ b = \sigma $ 或不。自從 $ b $ 是隨機的，這沒有透露任何關於 $ \sigma $ . 發件人安全性也很容易看出，留給讀者作為練習:) 總的來說，上面有兩輪，每個選定的 OT 都涉及三位通信。