Paper 2024/1254
Non-Interactive Zero-Knowledge from LPN and MQ
Abstract
We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (CRYPTO 2024), together with exponentially-hard MQ.
The main technical ingredient of our construction is an extremely natural (but only in hindsight!) construction of correlation-intractable (CI) hash functions from MQ, for a NIZK-friendly sub-class of constant-degree polynomials that we call concatenated constant-degree polynomials. Under exponential security, this hash function also satisfies the stronger notion of approximate CI for concatenated constant-degree polynomials. The NIZK construction then follows from a prior blueprint of Brakerski-Koppula-Mour (CRYPTO 2020). In addition, we show how to construct (approximate) CI hashing for degree-
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in CRYPTO 2024
- Keywords
- nizknon-interactive zero-knowledgepost-quantumlpnmqmultivariatecorrelation-intractability
- Contact author(s)
-
qvd @ andrew cmu edu
aayushja @ andrew cmu edu
zh jin @ northeastern edu - History
- 2024-08-09: approved
- 2024-08-08: received
- See all versions
- Short URL
- https://ia.cr/2024/1254
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1254, author = {Quang Dao and Aayush Jain and Zhengzhong Jin}, title = {Non-Interactive Zero-Knowledge from {LPN} and {MQ}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1254}, year = {2024}, url = {https://eprint.iacr.org/2024/1254} }