You are looking at a specific version 20180211:144457 of this paper.
See the latest version.
Paper 2018/167
On the Existence of Three Round Zero-Knowledge Proofs
Nils Fleischhacker and Vipul Goyal and Abhishek Jain
Abstract
We study the round complexity of zero-knowledge (ZK) proof systems. While five round ZK proofs for NP are known from standard assumptions [Goldreich-Kahan, J. Cryptology'96], Katz [TCC'08] proved that four rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of ZK proofs using non-black-box simulation. Our main result is that three round private-coin ZK proofs for NP do not exist (even w.r.t. non-black-box simulation), under certain assumptions on program obfuscation. Our approach builds upon the recent work of Kalai et al. [Crypto'17] who ruled out constant round public-coin ZK proofs under the same assumptions as ours.
Metadata
- Available format(s)
- Publication info
- Published by the IACR in EUROCRYPT 2018
- Keywords
- zero-knowledgeround complexitylower bound
- Contact author(s)
-
mail @ nilsfleischhacker de
abhishek @ cs jhu edu
goyal @ cs cmu edu - History
- 2018-02-11: received
- Short URL
- https://ia.cr/2018/167
- License
-
CC BY