Fiat-Shamir From Simpler Assumptions

Ran Canetti; Yilei Chen; Justin Holmgren; Alex Lombardi; Guy N.  Rothblum; Ron D.  Rothblum

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): PDF
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}
}