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

Version: 20220322:132557 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]