跳转到内容

不可区分混淆

维基百科,自由的百科全书

不可区分混淆(英语: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 assumptionLWE假设LPN假设英语Parity_learning#Noisy_version_("Learning_Parity_with_Noise")[4][1]此外,该构造还需要NC0英语NC_(complexity)#The NC hierarchy实现的超线性延展的伪随机数生成器[1]直至2006,即使只考虑亚线性延展的NC0伪随机数生成器,其存在性一直是未解问题。[5]

可能应用场合

若不可区分混淆器存在,它们可用于海量的密码学构造里。[2][4]具体地说,不可区分混淆器可用于以下的场合:

不过,iO不是万能的:例如,甚至在假设陷门排列英语trapdoor permutation的情况下,都无法通过黑盒构造由iO构造出抗撞英语Collision resistance密码杂凑函数,除非允许指数级的安全性损失[7]

参见

参考文献

  1. ^ 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. ^ 2.0 2.1 Klarreich, Erica. Cryptography Breakthrough Could Make Software Unhackable. Quanta Magazine. 2014-02-03 [2021-08-15]. (原始内容存档于2022-04-14). 
  3. ^ 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. ^ 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). 
  5. ^ 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. ^ 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). 
  7. ^ Asharov, Gilad; Segev, Gil. Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. 2015 [2021-08-15]. (原始内容存档于2022-01-21).