我們可以通過不經意傳輸 (OT) 協議將偽隨機函式 (PRF) 轉換為不經意 PRF (OPRF) 嗎？
我是一名軟體工程師，所以我通常認為是建構塊。而且我對 Crytography 中的數學符號不太熟悉，所以我會堅持使用函式呼叫和函式藍圖（我認為它們會很直覺）。
最近我一直在這裡詢問和閱讀幾個問題以及關於這些主題的一些相關論文。因此，我將嘗試首先列出我如何理解它們的定義；並提出使用 OT 和 PRF 的 OPRF 協議。
你能評論一下這個協議的有效性和安全性嗎？
這是我的定義，它們彼此獨立。
PRG
Alice 使用任意種子啟動 PRG。Alice 可以生成任意長度為 n 的隨機輸出。如果 Alice 在另一個時間，另一個系統將使用相同的種子為 PRG 播種，則輸出的前 n 位將與她之前獲得的輸出相同。
PRF
愛麗絲有一把鑰匙。Alice 用這個密鑰啟動她的 PRF。並且給定任意長度位的任何輸入，Alice 可以確定性地獲得任意長度為 k 的隨機輸出。（大小 k 和 n 不一定必須彼此有任何關係）
OT（特別是 1-2 OT）
Alice 創建了兩條長度相同（n 位）的消息 m0 和 m1。Bob 選擇 0 或 1 並獲得相應的消息。Alice 不知道 Bob 得到了哪一個，如果 Bob 選擇了 0，他將得到 m0，並且永遠不會知道 m1（反之亦然）
OPRF
Bob 有一個輸入。Alice 擁有 OPRF 功能的密鑰。在執行 OPRF 期間，Alice 根據 Bob 的輸入互動地生成一個看起來隨機的輸出，但是 Bob 的輸入對 Alice 是隱藏的。Alice 永遠不會知道 Bob 的輸入，Bob 也永遠不會知道 Alice 的密鑰。但是，如果 Alice 與 Bob 共享她的密鑰，或者 Bob 與 Alice 共享他的輸入，則可以重新生成相同的“隨機輸出”。
根據我列出的定義，我現在將嘗試提出一個滿足上述 OPRF 定義的協議。
我將首先提出一個幼稚且可能不太安全的版本；並嘗試解決我看到的安全問題，稍作改動。
Alice 有一個 PRG，這就是她使用它來建構 PRF 的方式。
//輸入和輸出是任意大小的位數組。
//輸出初始化為0（異或的標識元素）
prf(key, input[], output[]) { prg.setSeed(key) for(i = 0; i < input.length; i++) { bits0 = prg.nextBits(output.length) bits1 = prg.nextBits(output.length) if(input[i] == 0) output (XOR) bits0 else output (XOR) bits1 } }這種從 PRG 中創建 PRF 的方法建立在以下前提之上：
- XOR 操作將保留熵
- PRG 將生成沒有相關性的隨機序列。
現在 Bob 想要使用 Alice 的密鑰來使用這個 PRF。OPRF 如下。
- Bob 有一個大小為 n 的輸入，並且想要一個大小為 k 的隨機輸出
- Alice 用她的密鑰播種 PRG
- $$ OT $$他們為 Bob 輸入中的每一位執行 OT 協議
- $$ OT $$Alice 創建兩個大小為 k 位 {bits0, bits1} 的隨機消息
- $$ OT $$如果 Bob 輸入的目前 bit 為 0 Bob 選擇 bits0，否則選擇 bits1
- 最後 Bob XOR 的所有消息得到輸出。
該協議等效於上述 PRF。
上述協議將是安全的：
- 如果我們只執行這個協議一次
- 如果 Alice 每次執行都使用隨機密鑰
因為在第二次執行中，Bob 可以切換輸入中的位，並從 Alice 的 PRG 中學習完整的隨機序列。
然而，上述要求都不是現實的。使該協議安全的轉折如下：
- Alice 需要一個偶數大小的輸入
- Bob 有一個大小為 2n 的輸入，並且想要一個大小為 k 的隨機輸出
- 使用帶有一次性種子的 PRG，Alice 生成 n 個 k 位的隨機遮罩
- Alice 生成這 n 個遮罩的隨機排列，其中每條消息都只重複一次。（給我們一個大小為 2n 的序列，記住這是 Bob 輸入的大小）
- $$ OT $$現在，他們為 Bob 輸入中的每一位執行 OT 協議
- $$ OT $$Alice 創建兩個大小為 k 位 {bits0, bits1} 的隨機消息，並用序列 {bits0 (XOR) maskR, (bits1 (XOR) maskR} 中的下一個遮罩對它們進行異或運算
- $$ OT $$如果 Bob 輸入的目前位為 0 Bob 選擇遮罩位 0，否則選擇遮罩位 1
- 最後 Bob XOR 的所有消息。
由於遮罩將相互抵消，因此該協議的每次執行都將涉及一個隨機遮罩。這個協議應該仍然等同於上面定義的 PRF，並且不應該遇到之前協議中定義的問題。
我對這個 OPRF 的最終目標是將它用於 Private Set Intersection 協議。在問題中查看@Mikero 的答案：Alice 如何讓 Bob 在私有地圖中查找值
你能評論一下這個協議的有效性和安全性嗎？如果您發現它有任何缺點，我該如何改進它。
你所描述的聽起來很像本文中的編碼機制：
Benny Pinkas、Thomas Schneider、Michael Zohner：基於 OT 擴展的更快的私有集合交集，Usenix 2014。
請參閱該論文的第 5.1 節。基本上，Bob 輸入的每一位都有一個 OT 隨機字元串。Bob 對他的 OT 輸出進行異或運算。Alice 也可以為她的輸入計算相應的東西。
我不明白你的第二個協議在哪裡 $ 2n $ OT，我不清楚“maskR”的值。
無論如何，這個協議本身沒有任何問題。安全地測試兩個字元串的相等性很好。但它可以擴展到私有集合成員資格測試（Bob 有一個值，Alice 有很多。Bob 想知道他的項目是否在 Alice 的集合中。）如果你在最後散列這個 XOR 值。Alice 可以發送許多這樣的值，一個用於她的每個項目。如果沒有散列，多個 XOR 值的相關性會洩漏有關輸入的相關性。
您提到您喜歡根據定義明確的組件進行思考。如果您覺得僅限於使用普通的 1-out-of-2 OT，那麼這可能是建構適合 PSI 的 OPRF 的最佳方式。但是 PSI 最近的工作通過將 1-out-of-2 OT 推廣到更複雜的東西來獲得改進。甚至上面的論文也建議使用 1-out-of- $ N $ OT 更好（因為 OT 擴展的細節）。以下論文使用類似於 1-out-of- 的泛化 $ N $ OT 無界 $ N $ :
Vladimir Kolesnikov、Ranjit Kumaresan、Mike Rosulek、Ni Trieu。用於私有集合交集的高效批量不經意 PRF
使用這些概括，您不必為字元串的每一位做一個 OT，而是為每個基 - $ N $ 數字。在這種情況下 $ N $ 是無界的，你基本上只做一個“OT”。
基本上，如果我理解正確，您想創建一個協議，該協議允許 Alice 和 Bob 一起計算一個隨機值，而不會互相洩露他們的秘密（Alice 的密鑰和 Bob 的輸入）。如果是這樣，那麼已經有一種稱為Secret Sharing的協議的泛化。秘密共享協議的思想是計算一個只能使用密鑰獲得的秘密值。這些密鑰分佈在各方之間，並且每一方都不願意共享其密鑰。