Zero-Knowledge-Proofs
如果 IP 是它們來自的互動式證明系統類，為什麼零知識協議用於 NP 問題？
如標題所述，我正在研究 ZKP，我發現它們只是尊重零知識屬性的互動式證明系統。現在，如果這是真的，為什麼不將它們用於 IP 問題，即最初為它們引入的互動式證明系統的複雜性類別？我的意思是，證明者和驗證者之間的 ZKP 中的證明機制不是互動的嗎？那麼我們為什麼要討論與互動相反的 NP 問題呢？
原因是本質上， $ \mathcal IP $ 不在 $ \mathcal NP $ 無法用有效的證明者證明。由於我們通常對具有高效證明者的加密上下文感興趣，因此 ZK 的研究通常集中在 $ \mathcal NP $ . （請注意，在研究複雜性時，通常是在密碼學基礎中，我們當然對低效的證明者感興趣。）
為了看看為什麼在外面 $ \mathcal NP $ 證明者不能高效，請注意，任何具有高效證明者（給定見證人）的互動式證明都可以由接收見證人並在本地執行證明的機器模擬，測試結果是接受還是拒絕。這正是語言的類別 $ \mathcal MA $ . 在標準去隨機化假設下， $ \mathcal MA = NP $ . 因此，在這些假設下，任何不在 $ \mathcal NP $ 只能使用效率低下的證明者執行（甚至給它一些見證）。因此，在建構協議等時不太感興趣。