零知识证明系统：原理、效率与构造方法
1. 零知识证明相关结论
如果非一致单向置换存在，那么NP中的每个语言都有一个完美零知识论证。在零知识证明（ZK Proofs）和完美零知识论证（Perfect ZK Arguments）之间进行选择时，需要考虑以下因素：
-安全性和零知识属性的相对重要性：在特定应用中，如果某一属性具有明确的优先级，则应相应地做出选择。
-用户的计算资源：若某个用户拥有大量计算资源，可能希望确保其无法作弊，即使在信息论意义上也是如此。
-安全性和零知识属性的持续时间：安全性要求仅在执行期间有效，而在许多应用中，零知识属性可能在执行后很长时间内都很重要。在这种情况下，完美零知识论证具有明显优势。
2. 多项式对数效率的论证
通过结合认证树的思想和概率可检验证明（PCPs）的结果，可以显著提高NP零知识论证的效率。具体步骤如下：
1.问题转化：根据PCP定理，每个NP语言L都可以归约到3SAT问题。对于非L成员，它们会被映射到3CNF公式，每个真值赋值最多满足1 - ε比例的子句（ε > 0是一个通用常数）。记这个归约为f。为了证明x ∈ L，只需证明公式f(x)是可满足的。
2.验证过程：验证者无需检查f(x)的所有子句是否都被给定的赋值满足，只需均匀选择多项式对数数量的子句并检查赋值是否满足这些子句。如果x ∈ L且证明者提供了f(x)的满足赋值，验证者总是会接受；如果x ∉ L，没有赋值能满
