超多項式提取器對零知識證明安全性的影響

互動式零知識論證在三個部分被證明是安全的：

1. 完整性（如果證明者誠實，則驗證者接受）
2. 健全性（不誠實的證明者無法說服驗證者）
3. 零知識（證明不會向誠實的驗證者洩露任何資訊）

穩健性通常使用某種提取器來證明：通過回滾協議，通常多次重複，驗證者可以發送多個挑戰，並最終計算證明者持有的證人。

Benedikt Bünz 的這篇演講提到原始Bootle 的提取器存在問題，J. 等人。2016協議（Bulletproofs 的前身）：提取器在超多項式時間內執行。

提取器的超多項式複雜度有什麼影響？僅提取器的存在不足以表明證明者必須持有證人嗎？

提取器和知識背後的哲學是，如果證明者可以生成證明，那麼它本身就可以執行提取器。因此，如果它可以證明，那麼它就知道證人。

如果提取器在超多項式時間內執行，則證明者本身無法執行提取器。請注意，如果您將其發揮到極致，那麼在指數時間內總是可以找到證人。因此，任何 ZK 證明都可以說是具有指數時間提取器的知識證明。但這是沒有意義的。

從技術上講，使用這種零知識證明的協議的安全證明將會失效。

引用自：https://crypto.stackexchange.com/questions/88351