不可區分混淆

不可區分混淆（英語：Indistinguishability obfuscation，常作iO^[1]:1），是一種形式化定義了程式混淆的密碼原語（英语：Cryptographic primitive）。白話地說，混淆隱藏了程式的內部實現，但用戶仍可運行它。^[2]

候選構造

最早基於具體困難性假設（英语：Computational hardness assumption），可證安全（英语：Provable security）的候選構造在2013年提出。該假設和多线性映射（英语：Cryptographic multilinear map）有關，但後來該假設被推翻了。^[3][4]

一系列後續工作試圖將iO基於更標準的假設。賈殷（Jain）、林和薩海（英语：Amit sahai）於2020年出版的研究將iO建基於XDH假設（英语：XDH assumption）、LWE假設和LPN假設（英语：Parity_learning#Noisy_version_("Learning_Parity_with_Noise")）。^[4][1]此外，該構造還需要NC0（英语：NC_(complexity)#The NC hierarchy）實現的超線性延展的伪随机数生成器。^[1]直至2006，即使只考慮亞線性延展的NC0偽隨機數生成器，其存在性一直是未解問題。^[5]

可能應用場合

若不可區分混淆器存在，它們可用於海量的密碼學構造裡。^[2][4]具體地說，不可區分混淆器可用於以下的場合：

• 公钥密码学（以及其IND-CCA（英语：IND-CCA）—安全版本)^[6]
• 短数字签名^[6]
• IND-CCA（英语：IND-CCA）—安全的密鑰封裝（英语：Key encapsulation）方案^[6]
• 完美零知識的非交互零知識證明（英语：Non-interactive zero-knowledge proof）和簡賅的非交互論證（即證明方計算能力有限（英语：Computationally bounded adversary）的證明）^[6]
• 常數輪交互並行的零知識協議^[1]
• 有限多項式次數的多重線性映射 (密碼學)（英语：Cryptographic multilinear map）^[1]
• 單射陷門函數^[6]
• 全同态加密^[1]
• 見證加密^[1]
• 任何單調NP語言的秘密分享^[1]
• 半誠實不经意传输^[6]
• 抵賴加密（不論是發送者抵賴還是完全抵賴）^[6][1]
• 多方，非交互密钥交换^[1]
• 適應性安全簡賅的亂碼（Garbled）RAM^[1]
• RAM模型任意程式的不可區分混淆^[1]
• 關係難尋（Correlation intractible)函數^[1]
• 屬性加密^[1]
• PPAD（英语：PPAD (complexity)）困難性。^[1]

不過，iO不是萬能的：例如，甚至在假設陷門排列（英语：trapdoor permutation）的情況下，都無法通過黑盒構造由iO構造出抗撞（英语：Collision resistance）的密碼雜湊函數，除非允許指數級的安全性損失^[7]。

參見

• 黑箱混淆（英语：black-box obfuscation），一種更強，但一般情況下不可能實現的混淆形式。