不可区分混淆

不可区分混淆（英语：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）.