Journal of the ACM · 2012 · 161 citations · 19 references
ComputingComputer ScienceMathematicsComputer SecurityCryptographySecurity ProtocolsCryptographic ComplexityCryptographic ProtocolsProof ComplexityZero-knowledge ProofsArgument SystemsNon-interactive Zero-knowledge ProofsOpen QuestionsProof SystemsPublic-key EncryptionSecurity ProofsZero-knowledge Proof ProtocolsZero-knowledge Proof Systems
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.
19
Identity-Based Encryption from the Weil Pairing
Dan Boneh, Matthew Franklin · SIAM Journal on Computing · 2003 · 3.6K citations
Universally composable security: a new paradigm for cryptographic protocols
Ran Canetti · 2001 · 3.3K citations
A hard-core predicate for all one-way functions
Oded Goldreich, Leonid A. Levin · 1989 · 1.2K citations