不可區分混淆

不可區分混淆（英語：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]。

^ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 Jain, Aayush; Lin, Huijia; Sahai, Amit. Indistinguishability Obfuscation from Well-Founded Assumptions. 2020 [2021-08-15]. arXiv:2008.09317 . （原始內容存檔於2022-03-03）.
^ ^2.0 ^2.1 Klarreich, Erica. Cryptography Breakthrough Could Make Software Unhackable. Quanta Magazine. 2014-02-03 [2021-08-15]. （原始內容存檔於2022-04-14）.
^ Sanjam Garg; Craig Gentry; Shai Halevi; Mariana Raykova; Amit Sahai; Brent Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. FOCS 2013 (IEEE). 2013: 40–49. ISBN 978-0-7695-5135-7. doi:10.1109/FOCS.2013.13.
^ ^4.0 ^4.1 ^4.2 Klarreich, Erica. Computer Scientists Achieve 'Crown Jewel' of Cryptography. Quanta Magazine. 2020-10-10 [2021-08-15]. （原始內容存檔於2022-05-07）.
^ Applebaum, B; Ishai, Y; Kushilevitz, E. Cryptography in NC0 (PDF). SIAM Journal on Computing. 2006, 36 (4): 845–888 [2021-08-15]. doi:10.1137/S0097539705446950. （原始內容 (PDF)存檔於2021-11-30）.
^ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 ^6.6 Sahai, Amit; Waters, Brent. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. 2013 [2021-08-15]. （原始內容存檔於2022-02-03）.
^ Asharov, Gilad; Segev, Gil. Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. 2015 [2021-08-15]. （原始內容存檔於2022-01-21）.