證明任何語言都有一個有效的零知識證明L∈N磷大號∈ñ磷L in NP
讓 $ (P,V) $ 成為某種語言的有效零知識互動證明 $ A \in NP $ 那是 $ (T,\epsilon)-\text{sound} $ 和 $ (T,\epsilon)-\text{ZK} $ .
我想為每種語言展示這一點 $ L $ 可以簡化為 $ A $ 還有這麼高效的零知識互動證明 $ (P_2, V_2) $ 這也是 $ (T,\epsilon)-\text{sound} $ 和 $ (T,\epsilon)-\text{ZK} $ .
好吧，我不確定如何確切地開始描述這種 $ (P_2, V_2) $ ，但也許我不完全理解這一點，因為似乎只有一種簡單的方法。
自從 $ L $ 可簡化為 $ A $ , 那麼從 $ L $ 至 $ A $ . 即存在多項式算法 $ R $ 這樣 $ R(x) \in A \leftrightarrow x \in A $ , 並且有一個多項式算法 $ W $ 映射證人 $ w $ 為了 $ x \in L $ 給證人 $ W(x,w) $ 為了 $ R(x) \in A $ .
我的想法是採用證明系統 $ (P,V) $ 對於輸入 $ x $ 申請 $ R(x) $ 模擬原始的零知識證明 $ A $ .
然而，這對我來說似乎太微不足道了。而且，這樣我只得到 $ (T-|R|,\epsilon)-\text{sound} $ 和 $ (T-|R|,\epsilon)-\text{ZK} $ ，因為我需要執行算法 $ R $ .
幫助將不勝感激。
你的想法是正確的。雖然誠實證明者和驗證者的執行時間確實會隨著 $ R $ ，這（有點違反直覺）不會影響健全性和 ZK 的具體界限（至少它們通常是如何定義的）。
注意 $ T $ -對於證明系統來說，健全性並沒有真正意義，因為即使是無界的作弊證明者也是合理的。然而，它對於論證系統來說確實有意義，在這裡我們並沒有真正“失去”減少 $ R $ 的執行時間：任何 $ T $ -時間作弊證明者 $ P_2^* $ 例如 $ x \notin L $ 本身就是一個 $ T $ - 實例的時間作弊證明者 $ R(x) \notin A $ ，因為它愚弄了驗證者 $ V $ （對於語言 $ A $ ) 不做任何額外的計算。後者不是假設存在的，所以前者也不存在。
ZK 也有類似的推理： $ T $ -time 作弊驗證者 $ V_2^* $ 例如 $ x\in L $ 本身就是一個 $ T $ -time 作弊驗證器 $ R(x) \in A $ ，因為它的作用是 $ V $ 在與 $ P $ . 因此，我們不需要任何額外的計算來從與互動中“獲取知識” $ P $ 關於 $ R(x) $ .