Rate-1 Statistical Non-interactive Zero-Knowledge
摘要
We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the \(\textsf{circuitSAT}\) language, our construction achieves a proof length of \(|w| + |w|^\epsilon \cdot \textsf{poly}(\lambda )\) where w denotes the witness, \(\lambda \) is the security parameter, \(\epsilon \) is a constant less than 1, and \(\textsf{poly}(\cdot )\) is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from the sub-exponential hardness of either the LWE assumption, or the O(1)- \(\textsf{LIN}\) assumption on prime-order groups with efficiently computable bilinear maps, or the DDH assumption. Previously, Gentry et al. (Journal of Cryptology, 2015) achieved NIZKs with statistical soundness and computational zero-knowledge with the aforementioned proof length by relying on (circular-secure) Learning with Errors assumption.