New Techniques for Noninteractive Zero-Knowledge
Abstract
Noninteractive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including public-key encryption secure against chosen ciphertext attack, digital signatures, and various other cryptographic protocols. We introduce new techniques for constructing NIZK proofs based on groups with a bilinear map. Compared to previous constructions of NIZK proofs, our techniques yield dramatic reduction in the length of the common reference string (proportional to security parameter) and the size of the proofs (proportional to security parameter times the circuit size). Our novel techniques allow us to answer several long-standing open questions in the theory of noninteractive proofs. We construct the first perfect NIZK argument system for all NP. We construct the first universally composable NIZK argument for all NP in the presence of an adaptive adversary. We construct a non-interactive zap for all NP, which is the first that is based on a standard cryptographic security assumption.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2012
- Source ID
- 10.1145/2220357.2220358
Entities
People
- Amit Sahai
- Jens Groth
- Rafail Ostrovsky
Organizations
- Engineering and Physical Sciences Research Council
- National Science Foundation
- Office of Naval Research
- University College London
- University of California, Los Angeles