Welcome to the resource topic for 2022/370
Title:
Efficient NIZKs from LWE via Polynomial Reconstruction and ``MPC in the Head"
Authors: Riddhi Ghosal, Paul Lou, and Amit Sahai
Abstract:All existing works building non-interactive zero-knowledge (NIZK) arguments for \mathsf{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) \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 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 \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).
ePrint: https://eprint.iacr.org/2022/370
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .