Alex Lombardi: Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE
Friday, February 15, 2019 - 10:30am to 12:00pm
Location:
Hewlett, G882
Speaker:
Alex Lombardi
Seminar group:
Abstract: We construct non-interactive zero-knowledge (NIZK) arguments for 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. 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. This continues a recent line of works [Holmgren and Lombardi, FOCS '18; Canetti et al., ePrint '18] focused on instantiating special forms of correlation intractability and Fiat-Shamir under weaker 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 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. This continues a recent line of works [Holmgren and Lombardi, FOCS '18; Canetti et al., ePrint '18] focused on instantiating special forms of correlation intractability and Fiat-Shamir under weaker 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.
Joint work with Ran Canetti and Daniel Wichs