Constant-Round Concurrent Zero Knowledge from P-Certificates

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.

Authors

• Kai-Min Chung
• Huijia Lin
• Rafael Pass

Keywords

• Protocols
• Computational modeling
• Polynomials
• Awards activities
• Concurrent computing
• Complexity theory
• Security
• Zero Knowledge
• Hash Function
• Zero-knowledge Proof
• Interactive
• Standard Model
• Stage 2
• Original Protocol
• Simulation Techniques
• Simulated Activity
• Security Parameter
• Communication Rounds
• Proof Of Statement
• Number Of Executions
• Random Oracle
• Random Oracle Model
• Cryptography
• Concurrent Zero-Knowledge
• Non-Black-Box Technique