TY - GEN

T1 - Fiat-Shamir

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

AU - Canetti, Ran

AU - Chen, Yilei

AU - Holmgren, Justin

AU - Lombardi, Alex

AU - Rothblum, Guy N.

AU - Rothblum, Ron D.

AU - Wichs, Daniel

N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.

PY - 2019/6/23

Y1 - 2019/6/23

N2 - We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. As a consequence of our framework, we obtain the following concrete results. 1) There exists 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) There exists a non-interactive zero-knowledge argument system for NP in the common reference string model, under either of the following two assumptions: (i) Almost optimal hardness of search-LWE against polynomial-time adversaries, or (ii) The existence of a circular-secure FHE scheme with a standard (polynomial time, negligible advantage) level of security. 3) The classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP’89] is not zero knowledge when repeated in parallel, under any of the hardness assumptions above.

AB - We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. As a consequence of our framework, we obtain the following concrete results. 1) There exists 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) There exists a non-interactive zero-knowledge argument system for NP in the common reference string model, under either of the following two assumptions: (i) Almost optimal hardness of search-LWE against polynomial-time adversaries, or (ii) The existence of a circular-secure FHE scheme with a standard (polynomial time, negligible advantage) level of security. 3) The classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP’89] is not zero knowledge when repeated in parallel, under any of the hardness assumptions above.

KW - Cryptographic protocols

KW - Delegation of computation

KW - Fiat-Shamir heuristic

KW - Zero-knowledge protocols

UR - http://www.scopus.com/inward/record.url?scp=85065129547&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065129547&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316380

DO - 10.1145/3313276.3316380

M3 - Conference contribution

AN - SCOPUS:85065129547

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1082

EP - 1090

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

Y2 - 23 June 2019 through 26 June 2019

ER -