Rate-1 Statistical Non-Interactive Zero-Knowledge.

Summary

We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the circuitSAT language, our construction achieves a proof length of |w| + |w| ϵ · poly(λ) where w denotes the witness, λ is the security parameter, ϵ is a small constant less than 1, and poly(·) is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from either the LWE assumption, or the O(1)-LIN assumption on prime-order groups with efficiently computable bilinear maps, or the sub-exponential 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 the Learning with Errors (LWE) assumption