## Cryptology ePrint Archive: Report 2022/370

Efficient NIZKs from LWE via Polynomial Reconstruction and MPC in the Head"

Riddhi Ghosal and Paul Lou and Amit Sahai

Abstract: All existing methods of building non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from the Learning With Errors (LWE) assumption have relied on instantiating the Fiat-Shamir paradigm on a parallel repetition of an underlying honest-verifier zero knowledge (HVZK) $\Sigma$ protocol, via an appropriately built correlation-intractable (CI) hash function from LWE. This technique has inherent efficiency losses that arise from parallel repetition.

In this work, we build the first NIZK argument for $\mathsf{NP}$ from the LWE assumption that does not rely on parallel repetition. Instead, we show how to make use of the more efficient MPC in the Head'' technique for building an underlying honest-verifier protocol upon which to apply the Fiat-Shamir paradigm. The key to making this possible is a new construction of CI hash functions from LWE, using efficient algorithms for polynomial reconstruction as the main technical tool.

We stress that our work provides a new and more efficient base construction'' for building LWE-based NIZK arguments for $\mathsf{NP}$. Our protocol can be the building block around which other efficiency-focused bootstrapping techniques can be applied, such as the bootstrapping technique of Gentry et al. (Journal of Cryptology 2015).

Category / Keywords: cryptographic protocols /

Date: received 20 Mar 2022, last revised 20 Mar 2022

Contact author: riddhi at cs ucla edu, pslou at cs ucla edu, sahai at cs ucla edu

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2022/370

[ Cryptology ePrint archive ]