International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Rate-1 Statistical Non-Interactive Zero-Knowledge

Authors:
Pedro Branco , Bocconi University
Nico Döttling , CISPA
Akshayaram Srinivasan , University of Toronto
Download:
Search ePrint
Search Google
Conference: CRYPTO 2025
Abstract: 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|^\epsilon \cdot \mathsf{poly}(\lambda)$ where $w$ denotes the witness, $\lambda$ is the security parameter, $\epsilon$ is a constant less than 1, and $\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)$-$\mathsf{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.
BibTeX
@inproceedings{crypto-2025-35608,
  title={Rate-1 Statistical Non-Interactive Zero-Knowledge},
  publisher={Springer-Verlag},
  author={Pedro Branco and Nico Döttling and Akshayaram Srinivasan},
  year=2025
}