Paper 2024/1716 Original: eprint.iacr.org/2024/1716 ↗
Rate-1 Statistical Non-Interactive Zero-Knowledge
Abstract
We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the $\mathsf{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 $\mathsf{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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2025-05-30: last updated
- 2024-10-20: published
- Short URL
- https://ia.cr/2024/1716
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2024/1716,
author = {Pedro Branco and Nico Döttling and Akshayaram Srinivasan},
title = {Rate-1 Statistical Non-Interactive Zero-Knowledge},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1716},
year = {2024},
url = {https://eprint.iacr.org/2024/1716}
}