混淆大部分為零的函式
讓 $ f_k(x) $ 是具有兩個屬性的兩個參數的布爾函式：
- 功能 $ f $ 可以有效計算。
- 輸出始終為 0 或 1，並且對於任何固定的 $ k $ , 如果我們選擇 $ x $ 隨機， $ \Pr[f_k(x)=1] $ 很小（比如說，指數級地小）。
問題：有沒有通用的方法，給定 $ k $ ，混淆任意這樣的功能？換句話說，所有具有此屬性的函式都可以被混淆嗎？
這就是我所知道的。功能 $ f_k(x)=1 $ 如果 $ x=k $ 或者 $ 0 $ 否則可以混淆（稱為點函式）。功能 $ f_k(x)=1 $ 如果 $ d(k,x)<t $ 或者 $ 0 $ 否則可以混淆，其中 $ d(\cdot,\cdot) $ 是漢明距離和 $ t $ 是一個常數門檻值（參見 Juels 和 Sudhan 的模糊保險庫方案）。這些是滿足這些屬性並且可以被混淆的函式的簡單範例。也許這個類中的所有函式都可以被混淆？
我也知道沒有可以混淆所有函式的通用方案——但也許可以找到一個可以混淆此類中所有函式的通用方案。
動機：這將有助於驗證生物特徵。考慮到 $ k $ 作為使用者的模板，以及 $ x $ 作為送出給系統的生物特徵； $ f $ 驗證是否應該接受使用者。
密碼驗證是一個簡單的例子，對應於 $ f_k(x)=1 $ 當且當 $ x=k $ ; 這裡 $ k $ 是使用者設置帳戶時保存的密碼，以及 $ x $ 是使用者在認證過程中輸入的密碼。密碼散列是一種混淆此驗證功能的方法。模糊保險庫方案適用於我們認為感測器可能引入隨機位錯誤的生物辨識方案。但是還有其他生物辨識方案可能涉及驗證提議的生物辨識的更複雜的程序，我想知道是否有任何通用結果證明所有這些驗證方案都可以被混淆。
我可以接受任何合理的混淆形式（包括不可區分的混淆）。
我在下面提供了目前已知的（據我所知）關於混淆各種“大部分為零”函式的內容的摘要。
從難以區分的混淆
*我們可以混淆的東西：*所有有效的函式
*哪種安全概念：*不可區分性混淆
*基本假設：*新的、奇異的和相對知之甚少的假設。
*它有效率嗎？*沒有。
你在你的問題中說：
我也知道沒有可以混淆所有函式的通用方案——但也許可以找到一個可以混淆此類中所有函式的通用方案。
然而，據我們所知，所有有效計算的函式（因此特別是您感興趣的所有函式）完全有可能被 iO 方案混淆。我們有一堆具體的候選人，並且在基本假設方面進行了大量工作。提供完整的處理將超出該問題的範圍（自 2013 年以來，我統計了 160 多篇關於該主題的論文），但大致而言，所有已知的 iO 結構都依賴於奇異的假設：要麼存在分級編碼方案，其安全性是知之甚少，並且存在許多（許多）攻擊，最新的是這個, 或者最近關於一些極端低深度偽隨機發生器家族的弱偽隨機性的假設——在該領域的三個最新結果（1、2、3）中所做的一些假設已經被打破。此外，我們目前所知道的任何 iO 方案都不會是具體有效的。儘管如此，作為理論上的可行性結果，您關心的所有功能都可以被混淆（在異國情調的假設下），其中混淆安全概念是不可區分混淆的概念。
從多線性地圖
*我們可以混淆的東西：*迴避低次多項式模素數
*哪種安全概念：*虛擬黑盒混淆（最強的可能概念）
*基本假設：*新的、奇異的和相對知之甚少的假設。
*它有效率嗎？*沒有。
巴拉克等人。在本文中研究了為規避函式類實現更強大的混淆概念（例如虛擬灰盒混淆或虛擬黑盒混淆）的可能性。一類函式是迴避的，如果，對於任何固定輸入 $ x $ ，來自類的隨機函式計算為 $ 0 $ 上 $ x $ 以壓倒性的機率。雖然他們的結果主要是負面的，但 Barak 等人。還提供了一個有趣的積極結果：在一個新的完全隱藏的多線性編碼假設下，這與用於構造 iO 方案的假設相同（因此存在類似的弱點並給出可比較的（無效）效率），存在虛擬黑匣子用於測試低次多項式是否以某個大素數為模後計算為零的迴避函式的混淆器。虛擬黑盒混淆是混淆的終極安全概念：雖然 iO 聲明區分兩個功能等效的混淆電路應該是不可行的，但 VBB 聲明對手看到的所有內容，考慮到函式的 VBB 混淆，只能模擬給定黑盒訪問功能。眾所周知，VBB一般是不可能實現的；因此，這項工作表明，對於這類受限的規避函式來說，這種不可能性似乎不再存在。
來自 LWE
我們可以混淆的內容：連詞、計算和比較函式
*哪種安全概念：*分佈式虛擬黑盒
*基本假設：*經過充分研究的（推測的抗量子）LWE假設（或它的熵變體）
*它有效率嗎？*不是真的，但取決於要混淆的原語，它是可行的。
最近有大量工作確定了有趣的“大部分為零”函式類別，這些函式可以在簡單的（或變體）LWE 假設下被混淆，這是一個經過充分研究的假設。
1)**連詞。**有幾篇論文提出了混淆表單功能的方案
$ f : (x_1, \cdots, x_n) \rightarrow \bigwedge_{i \in I} y_i $ ,
其中每個 $ y_i $ 或者是 $ x_i $ 或者 $ 1-x_i $ ， 和 $ I $ 是的一個子集 $ [1, \cdots, n] $ . 本文展示瞭如何在環 LWE 假設的“熵變體”下混淆此類函式。混淆 64 位函式需要幾個小時，而評估經過混淆的程序需要幾秒鐘。實現的安全概念是分佈式 VBB 混淆，它是 VBB 混淆概念的變體，它也依賴於混淆函式的熵。
2)計算和比較函式。這是在本文和本文中獨立取得的一個非常好的結果。僅假設簡單的 LWE 假設，他們展示瞭如何計算一大類有趣的規避函式：具有兩個秘密值的函式 $ (\alpha, \beta) $ 硬編碼，並且在輸入時 $ x $ , 評估任意函式 $ f $ 上 $ x $ 和輸出 $ \alpha $ 當且僅當 $ f(x) = \beta $ （和 $ \bot $ 否則）。這擷取了特定情況下的連詞、點函式，還有更多。它們的構造還實現了分佈式虛擬黑盒混淆。
來自基於組的假設
*我們可以混淆的內容：*連詞、模式匹配、超平面成員資格
*哪種安全概念：*分佈式 VBB
*基本假設：*從熵 DDH 到泛群模型
*它有效率嗎？*它可以相當有效
許多結構也是在標準離散對數硬阿貝爾群的各種假設下設計的。最為顯著地：
1)連詞也可以在泛型組模型中被混淆，並實現分佈式 VBB，如最近這篇非常好的論文所示。
2）模式匹配。最近 的兩項工作已經考慮了使用“萬用字元”（即，模式可以包含對應於“任何值”的萬用字元*）對測試給定輸入字元串是否包含模式的函式進行混淆的任務，並實現模式的分佈式 VBB有一些熵。這些都是非常好的結果，而且與我目前討論的所有內容相比，效率也相對較高。第一篇論文在通用組模型中實現了安全性，而第二篇論文在標準模型中實現了安全性，在指數知識風格假設下（即，一些似是而非的東西，但遠不是最容易理解的假設）。
3)**超平面成員資格測試。**最後，本文展示瞭如何混淆超平面隸屬度測試（即檢查輸入向量是否屬於秘密的混淆超平面），它將點函式推廣到更大的類。混淆是相對有效的，並且在 DDH 假設的強變體下被證明是安全的。
注意：還存在用於重新加密函式的基於 DDH 的混淆方案，但這些方案不符合您的大多數零函式的概念。
從單向函式
*我們可以混淆的東西：*點函式
*哪種安全概念：*分佈式 VBB
*基本假設：*指數級強的單向函式、單向排列或確定性加密
*它有效率嗎？*是的
總結一下這個概述，你想要混淆的所有這些“大部分為零”函式中最弱的是點函式，除了特定點之外，它在所有地方都等於零。假設存在指數級強的單向函式（此處）或單向排列（此處）或確定性加密（此處） ，此類函式可以被混淆，具體取決於所實現的混淆的確切概念所有這些都是高度合理的假設（第二個甚至是密碼學的基本假設）。點函式的混淆已被深入研究，並在密碼學中有許多應用。請注意，要對點函式實現更強的混淆概念（例如，實現可組合性或不可延展性），通常依賴於更強的 DDH 類假設（例如，此處和此處）。