一個安全的函式評估問題和一個無意識轉移中的一個替代方案？

我正在考慮一個“安全功能評估”問題：

考慮兩方：A 和 B。A 具有一對一的映射函式 $ f(x)=k $ . 基本上，函式 $ f(x) $ 可以看成是一張兩列的表。第一列是域 $ x $ 表示為 $ D $ . 第二列是范圍 $ K $ . 乙方有秘密輸入 $ x_i\in D $ . B 發送它的輸入 $ x_i $ 到 A 和 A 會返回對應的 $ k_i $ 給 B。

要求是 A 對輸入一無所知 $ x_i $ 和輸出 $ k_i $ . B 對函式一無所知 $ f(x) $ .

1. 對於上述問題，一個可能的解決方案是 1-out-of-n 不經意轉移。但是，當域（或表）的大小很大時。使用不經意傳輸將引入繁重的計算和通信成本。
2. 我能想到的另一個可能的解決方案是將函式建模為電路。然後可能會使用一些技術，例如亂碼電路。

我認為上述問題在密碼學界已經考慮了很長時間。關於這個問題的任何相關工作或想法都會有所幫助。特別是，有沒有一種替代方法可以提高其效率？

該問題在文獻中被稱為私有函式評估(PFE)。發件人有輸入（一個功能） $ f $ ; 接收器有輸入 $ x $ ，並且只有接收者學習 $ f(x) $ .

• 如果您願意洩露計算電路的拓撲 $ f $ （但不是門的身份），然後使用經典的亂碼電路/姚的協議將起作用。眾所周知，這些亂碼電路結構會隱藏門功能。您只是不能在亂碼電路中使用最新的優化（從 free-XOR 開始），因為它們會洩漏哪些門計算 XOR 而哪些不計算。
• 如果您願意洩漏（上限）計算電路中的門數 $ f $ ，然後你可以做一個通用電路的標準SFE。通用電路 $ U $ 將電路的描述作為輸入 $ C $ , 和一個輸入 $ x $ , 和輸出 $ U(C,x) = C(x) $ . 允許 $ C $ 具有 $ n $ 門，大小 $ U $ 必須至少 $ \Omega(n \log n) $ . Valiant 描述了一個達到這個尺寸的結構，但它顯然是一個非常複雜的結構。有一個更簡單的尺寸結構 $ O(n \log^2 n) $ Kolesnikov & Schneider 的常數很小。

Leslie Valiant：通用電路（初步報告），STOC 1976

Vlad Kolesnikov 和 Thomas Schneider：實用的通用電路構造和私有功能的安全評估，金融密碼學 2008

• Mohassel 和 Sadeghian 提出了一些最近的 PFE 方法，它們避免了通用電路並具有線性成本 $ O(n) $ . 如上，協議洩露了電路計算中的門數 $ f $ . 我不知道這些協議在實踐中如何與通用電路協議相提並論。除了下面的，還有一個實現主動安全的後續工作。

Payman Mohassel 和 Saaed Sadeghian：如何在 MPC 中隱藏電路：私有功能評估的有效框架，Eurocrypt 2013。

• 如果你願意洩露這個事實 $ f $ 有一些其他特殊的代數結構（例如，它是一個線性函式），那麼肯定有一些方法可以利用該結構來獲得更有效的解決方案。

否則，如果你不願意洩露任何關於 $ f $ 那麼你真的沒有什麼比 1-out-of- 更好的了 $ n $ 舊約。如果 $ f $ 可以是一個完全隨機的映射，那麼就沒有 $ f $ 這比它的真值表要簡潔得多。

引用自：https://crypto.stackexchange.com/questions/29140