不可區分性混淆是真的嗎？
我最近偶然發現了一篇有趣的廣達雜誌文章。它指出，不可區分性混淆 (iO) 的理論可行性已經得到證明，參考了Jain、Lin 和 Sahai的一篇相對較新的論文。但是，iO 的 Wikipedia 文章指出，本文中介紹的工作依賴於“可疑”假設，即存在 PRNG $ NC^0 $ . 該論文的作者明確列出了這個假設，但讓我在這裡絆倒的是維基百科文章的措辭。我查看了維基百科文章中引用的論文。我在密碼學方面有一些基礎知識，在復雜性理論方面有一些更精煉的知識，但還不足以完全理解這兩個出版物中的任何一個。然而，我從 Applebaum 的論文中了解到，關於上述 PRNG 存在的問題間接涉及 $ P−NP $ 問題，讓我覺得這是一個不太可能很快解決的問題。
所以我現在對 Quanta Magazine 文章的可靠性感到非常困惑。正如您現在可能已經收集到的那樣，我不是來自密碼學領域。但我從文章中得知，這項技術（如果真的可行的話）可能會徹底改變我們對加密協議的看法，這讓我想知道為什麼它沒有掀起更大的波瀾。
我的問題是：IO 的證明是否可靠（即，現在可以安全地說 IO 在理論上是可能的，忽略實際實施和應用的所有麻煩），還是基於一些目前無法驗證的假設?
首先，維基百科文章指出，該假設需要一個具有指數拉伸的 PRG。這是不正確的，我已經編輯了這篇文章。相反，要求是在 $ NC_0 $ 具有超線性拉伸（即，從 $ n $ 至 $ n^{1+\tau} $ 對於任何 $ \tau>0 $ ）。這確實是未知的，據我通過簡短的搜尋可以確定，但如果你真的有興趣，我建議你聯繫 Benny Applebaum 並詢問他關於這個問題的目前狀態。請注意，論文中的其他假設也非常強大，但比我們迄今為止所擁有的一切都更加合理。那麼，我們能否說我們擁有 iO，除非我們相信很多加密貨幣會被打破？可能還沒有。但我們現在離那個更近了。
請注意，某些事物的存在與 P/NP 和其他問題有關這一事實並不意味著任何事情。幾乎所有的加密都依賴於假設（例如，如果 $ P=NP $ ）。問題只是這些假設是否是我們所說的“標準”。