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 - Funding Information:
RC is supported by NSF awards 1413920 and 1801564, ISF award 1523/14. Research was conducted while YC was at Boston University supported by the NSF MACS project and NSF grant CNS-1422965. Research was conducted in part while JH was at MIT, supported in part by the NSF MACS project. AL is supported in part by an NDSEG fellowship, as well as by NSF Grants CNS-1350619 and CNS-1414119, and by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236. GR is supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702). Parts of this research were conducted while RR was at MIT and Northeastern. RR is supported in part by the Israeli Science Foundation (Grant No. 1262/18). DW is supported by NSF grants CNS-1314722, CNS-1413964, CNS-1750795 and the Alfred P. Sloan Research Fellowship.
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 -