CryptoDB
Efficient NIZKs from LWE via Polynomial Reconstruction and ``MPC in the Head''
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2022 |
| 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) 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 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). |
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32591,
title={Efficient NIZKs from LWE via Polynomial Reconstruction and ``MPC in the Head''},
publisher={Springer-Verlag},
author={Paul Lou and Riddhi Ghosal and Amit Sahai},
year=2022
}