Concurrent Zero Knowledge with Logarithmic Round-Complexity

We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.

Authors

• Manoj Prabhakaran 0001
• Alon Rosen
• Amit Sahai

Keywords

• Polynomials
• Cryptographic protocols
• Internet
• Interleaved codes
• Buildings
• Access protocols
• Computer science
• Computational modeling
• Analytical models
• Computer simulation
• Zero Knowledge
• One-way Function
• Zero-knowledge Proof
• Interactive
• Recent Results
• Common Input
• Message Length
• Protocol Stage
• Random String
• Protocol Execution
• Hybrid Simulation
• Initial Commitment
• Probabilistic Polynomial Time