Paper 2018/1004
Fiat-Shamir From Simpler Assumptions
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum
Abstract
We present two new protocols: (1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem. (2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries. Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions (specifically, correlation intractable functions) to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- alexjl @ mit edu
- History
- 2018-10-23: last of 2 revisions
- 2018-10-22: received
- See all versions
- Short URL
- https://ia.cr/2018/1004
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/1004, author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N. Rothblum and Ron D. Rothblum}, title = {Fiat-Shamir From Simpler Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1004}, year = {2018}, url = {https://eprint.iacr.org/2018/1004} }