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

Riddhi Ghosal; Paul Lou; Amit Sahai

Paper 2022/370

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

Riddhi Ghosal

Paul Lou

Amit Sahai

Abstract

All existing works building non-interactive zero-knowledge (NIZK) arguments for $NP$ from the Learning With Errors (LWE) assumption have studied instantiating the Fiat-Shamir paradigm on a parallel repetition of an underlying honest-verifier zero knowledge (HVZK) $Σ$ 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 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. To make this possible, we provide a new and more efficient 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 . 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).

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): riddhi @ cs ucla edu
pslou @ cs ucla edu
sahai @ cs ucla edu
History: 2022-06-01: revised; 2022-03-22: received; See all versions
Short URL: https://ia.cr/2022/370
License: CC BY

BibTeX

@misc{cryptoeprint:2022/370,
      author = {Riddhi Ghosal and Paul Lou and Amit Sahai},
      title = {Efficient {NIZKs} from {LWE} via Polynomial Reconstruction and ``{MPC} in the Head"},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/370},
      year = {2022},
      url = {https://eprint.iacr.org/2022/370}
}