Multiparty-Computation
是否有可能建構一個通信複雜度小於發送者整個輸入的 N 中 1 的 OT？
1-out-of-的結構 $ n $ 舊約 $ l $ 我見過的-bit字元串的通信複雜度與 $ nl $ . 我想知道，是否可以在主動安全的情況下進行 OT，並且轉移少於 $ O(nl) $ 位（我忽略了安全參數 $ O $ -這裡的符號）？對我來說重要的部分是讓它比僅僅將發送者的輸入傳輸到接收者更便宜。
是否存在一些固有限制，不允許這種 OT 傳輸比發送者輸入更少的比特？是否有任何溝通下限？
假設發送者有字元串 $ x_1, \ldots, x_n $ , 每個長度 $ \ell $ . 接收方有選擇 $ y \in {1, \ldots, n} $ 並想學習（僅） $ x_y $ . 該協議可以進行如下：
- 接收方生成密鑰 $ k $ 對於對稱密鑰完全同態加密方案。
- 接收方發送 $ c = \textsf{Enc}(k,y) $ .
- 發送者想像一個布爾電路 $ f $ 對於函式 $ y \mapsto x_y $ - 這個電路有所有的 $ x_i $ 內置的值。
- Sender 使用同態評估特徵進行本地計算 $ c’ = \textsf{Enc}(k,f(y)) $ .
- 發件人發送 $ c’ $ .
- 接收方解密得到 $ f(y) = x_y $ .
只有兩個密文（每個加密一個 $ \ell $ -bit string) 被發送，所以這可能會花費 $ O(\kappa)+2\ell $ 位用於合適的 FHE 方案。注意：您需要一個電路專用的加密方案 - 即， $ c’ $ 應該顯示不超過 $ f(y) $ ，甚至是鑰匙持有人。
該協議對半誠實的對手是安全的，但也有一些方法可以將其擴展到惡意安全。
為了補充 Mikero 的回答：
- 如果你想要 1-of- $ N $ OT 選擇的輸入位，已知的獲取方法 $ o(N) $ 通信建立在亞線性私人資訊檢索的工作之上。大多數解決方案都依賴於完全同態加密，就像 Mikero 的回答一樣。然而，在其他密碼學假設下也存在各種替代結構，例如DCR（通過 Damgård-Jurik 密碼系統）或DDH 和 QR（使用陷門散列函式）。
- 如果你想要 1-of- $ N $ 偽隨機OT（即 $ N $ 發送方的輸入是一些偽隨機函式的輸出），那麼在 LPN 假設的變體下有替代的、更有效的解決方案，參見例如這個工作。
- 存在（許多）零知識知識證明的構造以及見證人大小的亞線性通信。如果您希望它們非互動，則需要強假設（隨機預言模型，或 SNARG），但如果您對互動很好，它們存在於與存在抗衝突雜湊函式一樣簡單的假設（例如此處）。您可以以通用方式使用任何此類證明系統，將半誠實的 OT（例如 Mikero 的答案中的那個）轉換為具有主動安全性的方案。
- 如果你只想做 1-out-of- $ N $ 在通信小於數據庫大小的情況下，這在一般假設下是可能的（儘管通信只會稍微少一點）：存在陷門排列（參見此處）。為了主動安全，您還需要 CRHF。