不可区分混淆
 | 此条目包含过多行话或专业术语，可能需要简化或提出进一步解释。 (2021年8月1日) |
不可区分混淆（英语：Indistinguishability obfuscation，常作iO[1]:1），是一种形式化定义了程式混淆的密码原语。白话地说，混淆隐藏了程式的内部实现，但用户仍可运行它。[2]
候选构造
[编辑]最早基于具体困难性假设，可证安全的候选构造在2013年提出。该假设和多线性映射有关，但后来该假设被推翻了。[3][4]
一系列后续工作试图将iO基于更标准的假设。贾殷（Jain）、林和萨海于2020年出版的研究将iO建基于XDH假设、LWE假设和LPN假设。[4][1]此外，该构造还需要NC0实现的超线性延展的伪随机数生成器。[1]直至2006，即使只考虑亚线性延展的NC0伪随机数生成器，其存在性一直是未解问题。[5]
可能应用场合
[编辑]若不可区分混淆器存在，它们可用于海量的密码学构造里。[2][4]具体地说，不可区分混淆器可用于以下的场合：
- 公钥密码学（以及其IND-CCA—安全版本)[6]
- 短数字签名[6]
- IND-CCA—安全的密钥封装方案[6]
- 完美零知识的非交互零知识证明和简赅的非交互论证（即证明方计算能力有限的证明）[6]
- 常数轮交互并行的零知识协议[1]
- 有限多项式次数的多重线性映射 (密码学)[1]
- 单射陷门函数[6]
- 全同态加密[1]
- 见证加密[1]
- 任何单调NP语言的秘密分享[1]
- 半诚实不经意传输[6]
- 抵赖加密（不论是发送者抵赖还是完全抵赖）[6][1]
- 多方，非交互密钥交换[1]
- 适应性安全简赅的乱码（Garbled）RAM[1]
- RAM模型任意程式的不可区分混淆[1]
- 关系难寻（Correlation intractible)函数[1]
- 属性加密[1]
- PPAD困难性。[1]
不过，iO不是万能的：例如，甚至在假设陷门排列的情况下，都无法通过黑盒构造由iO构造出抗撞的密码杂凑函数，除非允许指数级的安全性损失[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）.
