TY - GEN
T1 - New techniques for zero-knowledge
T2 - 40th Annual International Cryptology Conference, CRYPTO 2020
AU - Ball, Marshall
AU - Dachman-Soled, Dana
AU - Kulkarni, Mukul
N1 - Funding Information:
improve this work. The first author is supported in part by an IBM Research PhD Fellowship. This work is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006 and by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001120C0085. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, DAPRA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. The second and third authors are supported in part by NSF grants #CNS-1933033, #CNS-1840893, #CNS-1453045 (CAREER), by a research partnership award from Cisco and by financial assistance award 70NANB15H328 and 70NANB19H126 from the U.S. Department of Commerce, National Institute of Standards and Technology.
Funding Information:
We thank Tal Malkin for helpful discussions and suggestions to improve this work. The first author is supported in part by an IBM Research PhD Fellowship. This work is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006 and by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001120C0085. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, DAPRA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. The second and third authors are supported in part by NSF grants #CNS-1933033, #CNS-1840893, #CNS-1453045 (CAREER), by a research partnership award from Cisco and by financial assistance award 70NANB15H328 and 70NANB19H126 from the U.S. Department of Commerce, National Institute of Standards and Technology.
Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - We present a transformation from NIZK with inefficient provers in the uniform random string (URS) model to ZAPs (two message witness indistinguishable proofs) with inefficient provers. While such a transformation was known for the case where the prover is efficient, the security proof breaks down if the prover is inefficient. Our transformation is obtained via new applications of Nisan-Wigderson designs, a combinatorial object originally introduced in the derandomization literature. We observe that our transformation is applicable both in the setting of super-polynomial provers/poly-time adversaries, as well as a new fine-grained setting, where the prover is polynomial time and the verifier/simulator/zero knowledge distinguisher are in a lower complexity class, such as NC1. We also present NC1-fine-grained NIZK in the URS model for all of NP from the worst-case assumption (Formula Presented). Our techniques yield the following applications: 1.ZAPs for AM from Minicrypt assumptions (with super-polynomial time provers),2.NC1-fine-grained ZAPs for NP from worst-case assumptions,3.Protocols achieving an “offline” notion of NIZK (oNIZK) in the standard (no-CRS) model with uniform soundness in both the super-polynomial setting (from Minicrypt assumptions) and the NC1-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.
AB - We present a transformation from NIZK with inefficient provers in the uniform random string (URS) model to ZAPs (two message witness indistinguishable proofs) with inefficient provers. While such a transformation was known for the case where the prover is efficient, the security proof breaks down if the prover is inefficient. Our transformation is obtained via new applications of Nisan-Wigderson designs, a combinatorial object originally introduced in the derandomization literature. We observe that our transformation is applicable both in the setting of super-polynomial provers/poly-time adversaries, as well as a new fine-grained setting, where the prover is polynomial time and the verifier/simulator/zero knowledge distinguisher are in a lower complexity class, such as NC1. We also present NC1-fine-grained NIZK in the URS model for all of NP from the worst-case assumption (Formula Presented). Our techniques yield the following applications: 1.ZAPs for AM from Minicrypt assumptions (with super-polynomial time provers),2.NC1-fine-grained ZAPs for NP from worst-case assumptions,3.Protocols achieving an “offline” notion of NIZK (oNIZK) in the standard (no-CRS) model with uniform soundness in both the super-polynomial setting (from Minicrypt assumptions) and the NC1-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.
UR - http://www.scopus.com/inward/record.url?scp=85089722637&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089722637&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-56877-1_24
DO - 10.1007/978-3-030-56877-1_24
M3 - Conference contribution
AN - SCOPUS:85089722637
SN - 9783030568764
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 674
EP - 703
BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, Proceedings
A2 - Micciancio, Daniele
A2 - Ristenpart, Thomas
PB - Springer
Y2 - 17 August 2020 through 21 August 2020
ER -