CryptoDB
Which Languages Have 4-Round Fully Black-Box Zero-Knowledge Arguments from One-Way Functions?
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2020 |
| Abstract: | We prove that if a language $\cL$ has a 4-round fully black-box zero-knowledge argument with negligible soundness based on one-way functions, then $\overline{\cL} \in \MA$. Since $\coNP \subseteq \MA$ implies that the polynomial hierarchy collapses, our result implies that $\NP$-complete languages are unlikely to have 4-round fully black-box zero-knowledge arguments based on one-way functions. In TCC 2018, Hazay and Venkitasubramaniam, and Khurana, Ostrovsky, and Srinivasan demonstrated 4-round fully black-box zero-knowledge arguments for all languages in $\NP$ based on injective one-way functions. Their results also imply a 5-round protocol based on one-way functions. In essence, our result resolves the round complexity of fully black-box zero-knowledge arguments based on one-way functions. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30217,
title={Which Languages Have 4-Round Fully Black-Box Zero-Knowledge Arguments from One-Way Functions?},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={One-Way Functions;Zero-Knowledge Arguments;Black-Box Constructions},
volume={12105},
doi={10.1007/978-3-030-45727-3_20},
author={Carmit Hazay and Rafael Pass and Muthuramakrishnan Venkitasubramaniam},
year=2020
}