Cryptology ePrint Archive: Report 2018/1248

Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)

Ran Canetti and Alex Lombardi and Daniel Wichs

Abstract: We construct non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from any circular-secure fully homomorphic encryption (FHE) scheme. In particular, we obtain such NIZKs under a circular-secure variant of the learning with errors (LWE) problem while only assuming a standard (poly/negligible) level of security. Our construction can be modified to obtain NIZKs which are either: (1) statistically zero-knowledge arguments in the common random string model or (2) statistically sound proofs in the common reference string model.

We obtain our result by constructing a new correlation-intractable hash family [Canetti, Goldreich, and Halevi, JACM~'04] for a large class of relations, which suffices to apply the Fiat-Shamir heuristic to specific 3-message proof systems that we call ``trapdoor $\Sigma$-protocols.'' In particular, assuming circular secure FHE, our hash function $h$ ensures that for any function $f$ of some a-priori bounded circuit size, it is hard to find an input $x$ such that $h(x)=f(x)$. This continues a recent line of works aiming to instantiate the Fiat-Shamir methodology via correlation intractability under progressively weaker and better-understood assumptions. Another consequence of our hash family construction is that, assuming circular-secure FHE, the classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP~'89] is not zero knowledge when repeated in parallel.

We also show that, under the plain LWE assumption (without circularity), our hash family is a universal correlation intractable family for general relations, in the following sense: If there exists any hash family of some description size that is correlation-intractable for general (even inefficient) relations, then our specific construction (with a comparable size) is correlation-intractable for general (efficiently verifiable) relations.

Category / Keywords:

Original Publication (with major differences): STOC 2019

Date: received 31 Dec 2018, last revised 20 Jun 2019

Contact author: alexjl at mit edu

Available format(s): PDF | BibTeX Citation

Note: A merge of this work with ePrint:2018/1004 appears in STOC 2019.

Version: 20190620:083816 (All versions of this report)

Short URL: ia.cr/2018/1248


[ Cryptology ePrint archive ]