Cryptology ePrint Archive: Report 2018/1004

Fiat-Shamir From Simpler Assumptions

Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and 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.

Category / Keywords:

Date: received 17 Oct 2018, last revised 23 Oct 2018

Contact author: alexjl at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20181023:071610 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]