Jens Groth
Rafail Ostrovsky
Skip Abstract Section
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.
- Abe, M. and Fehr, S. 2007. Perfect NIZK with adaptive soundness. In Theory of Cryptography - 4th Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science Series, vol. 4392, 118--136. Google Scholar
Digital Library
- Aiello, W. and Håstad, J. 1991. Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42, 3, 327--345. Google ScholarDigital Library
- Barak, B., Ong, S. J., and Vadhan, S. P. 2007. Derandomization in cryptography. SIAM J. Comput. 37, 2, 380--400. Google ScholarDigital Library
- Bellare, M., Hofheinz, D., and Yilek, S. 2009. Possibility and impossibility results for encryption and commitment secure under selective opening. In Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 5479, 1--35. Google ScholarDigital Library
- Blum, M., Feldman, P., and Micali, S. 1988. Non-interactive zero-knowledge and its applications. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 103--112. Google ScholarDigital Library
- Blum, M., De Santis, A., Micali, S., and Persiano, G. 1991. Noninteractive zero-knowledge. SIAM J. Comput. 20, 6, 1084--1118. Google ScholarDigital Library
- Boneh, D. and Franklin, M. K. 2003. Identity-based encryption from the Weil pairing. SIAM J. Comput. 32, 3, 586--615. Google ScholarDigital Library
- Boneh, D., Boyen, X., and Shacham, H. 2004. Short group signatures. In Proceedings of the 24th Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 3152, 41--55.Google ScholarCross Ref
- Boneh, D., Goh, E.-J., and Nissim, K. 2005. Evaluating 2-DNF formulas on ciphertexts. In Proceedings of the 2nd Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science Series, vol. 3378, 325--341. Google ScholarDigital Library
- Boyar, J., Damgård, I., and Peralta, R. 2000. Short non-interactive cryptographic proofs. J. Cryptology 13, 4, 449--472.Google ScholarDigital Library
- Boyen, X. and Waters, B. 2006. Compact group signatures without random oracles. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 4004, 427--444. Google ScholarDigital Library
- Boyen, X. and Waters, B. 2007. Full-domain subgroup hiding and constant-size group signatures. In Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC). Lecture Notes in Computer Science Series, vol. 4450, 1--15. Google ScholarDigital Library
- Brassard, G. and Crèpeau, C. 1986. Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 188--195. Google ScholarDigital Library
- Brassard, G., Chaum, D., and Crèpeau, C. 1988. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37, 2, 156--189. Google ScholarDigital Library
- Canetti, R. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 136--145. Google ScholarDigital Library
- Canetti, R., Feige, U., Goldreich, O., and Naor, M. 1996. Adaptively secure multi-party computation. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 639--648. Google ScholarDigital Library
- Canetti, R., Lindell, Y., Ostrovsky, R., and Sahai, A. 2002. Universally composable two-party and multi-party secure computation. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 494--503. Google ScholarDigital Library
- Damgård, I. 1992. Non-interactive circuit based proofs and non-interactive perfect zero-knowledge with preprocessing. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 658, 341--355. Google ScholarDigital Library
- Damgård, I. and Nielsen, J. B. 2002. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In Proceedings of the 22nd Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 2442, 581--596. Google ScholarDigital Library
- De Santis, A., Di Crescenzo, G., Persiano, G., and Yung, M. 1998. Image density is complete for non-interactive-SZK. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science Series, vol. 1443, 784--795. Google ScholarDigital Library
- De Santis, A., Di Crescenzo, G., and Persiano, G. 1999. Non-interactive zero-knowledge: A low-randomness characterization of NP. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science Series, vol. 1644, 271--280. Google ScholarDigital Library
- De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., and Sahai, A. 2002. Robust non-interactive zero knowledge. In Proceedings of the 22nd Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 2139, 566--598. Google ScholarDigital Library
- Dolev, D., Dwork, C., and Naor, M. 2000. Non-malleable cryptography. SIAM J. Comput. 30, 2, 391--437. Google ScholarDigital Library
- Dwork, C. and Naor, M. 2000. Zaps and their applications. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 283--293. Google ScholarDigital Library
- Feige, U., Lapidot, D., and Shamir, A. 1999. Multiple non-interactive zero knowledge proofs under general assumptions. SIAM J. Comput. 29, 1, 1--28. Google ScholarDigital Library
- Fortnow, L. 1987. The complexity of perfect zero-knowledge. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 204--209. Google ScholarDigital Library
- Garay, J. A., MacKenzie, P. D., and Yang, K. 2006. Strengthening zero-knowledge protocols using signatures. J. Crypt. 19, 2, 169--209. Google ScholarDigital Library
- Goldreich, O. and Levin, L. A. 1989. A hard-core predicate for all one-way functions. In Proceedings of the ACM Symposium on Theory of Computing (STOC).25--32. Google ScholarDigital Library
- Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 3, 691--729. Google ScholarDigital Library
- Goldreich, O., Ostrovsky, R., and Petrank, E. 1998. Computational complexity and knowledge complexity. SIAM J. Comput. 27, 1116--1141. Google ScholarDigital Library
- Goldreich, O., Sahai, A., and Vadhan, S. P. 1999. Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In Proceedings of the 19th Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 1666, 467--484. Google ScholarDigital Library
- Groth, J. 2006. Simulation-sound NIZK proofs for a practical language and constant size group signatures. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Lecture Notes in Computer Science Series, vol. 4248, 444--459. Google ScholarDigital Library
- Groth, J. 2010. Short non-interactive zero-knowledge proofs. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Lecture Notes in Computer Science Series, vol. 6477, 341--358.Google ScholarCross Ref
- Groth, J. and Sahai, A. 2008. Efficient non-interactive proof systems for bilinear groups. In Proceedings of the 17th Annual International Conference on the Theory and Application of Crytographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 4965, 415--432. Google ScholarDigital Library
- Groth, J., Ostrovsky, R., and Sahai, A. 2006a. Non-interactive zaps and new techniques for NIZK. In Proceedings of the 26th Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 4117, 97--111. Google ScholarDigital Library
- Groth, J., Ostrovsky, R., and Sahai, A. 2006b. Perfect non-interactive zero-knowledge for NP. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 4004, 339--358. Google ScholarDigital Library
- Hemenway, B. and Ostrovsky, R. 2010. Building injective trapdoor functions from oblivious transfer. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC) 17. 127.Google Scholar
- Hemenway, B., Libert, B., Ostrovsky, R., and Vergnaud, D. 2011. Lossy encryption: Constructions from general assumptions and efficient selective opening chosen ciphertext security. In Proceedings of ASIACRYPT. Lecture Notes in Computer Science Series, vol. 7073, 70--88. Google ScholarDigital Library
- Kilian, J. and Petrank, E. 1998. An efficient noninteractive zero-knowledge proof system for NP with general assumptions. J. Crypt. 11, 1, 1--27.Google ScholarDigital Library
- Kol, G. and Naor, M. 2008. Cryptography and game theory: Designing protocols for exchanging information. In Proceedings of the 5th Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science Series, vol. 4948, 320--339. Google ScholarDigital Library
- MacKenzie, P. D. and Yang, K. 2004. On simulation-sound trapdoor commitments. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science Series, vol. 3027, 382--400.Google ScholarCross Ref
- Naor, M. 2003. On cryptographic assumptions and challenges. In Proceedings of the Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 2729, 96--109.Google ScholarCross Ref
- Ostrovsky, R. 1991. One-way functions, hard on average problems, and statistical zero-knowledge proofs. In Proceedings of the Structure in Complexity Theory Conference. 133--138.Google ScholarCross Ref
- Pass, R. 2003. On deniability in the common reference string and random oracle model. In Proceedings of the Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 2729, 316--337.Google ScholarCross Ref
- Pass, R. and Shelat, A. 2005. Unconditional characterizations of non-interactive zero-knowledge. In Proceedings of the Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 3621, 118--134. Google ScholarDigital Library
- Pedersen, T. P. 1991. Non-interactive and information-theoretic secure verifiable secret sharing. In Proceedings of the Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 576, 129--140. Google ScholarDigital Library
- Peikert, C., Vaikuntanathan, V., and Waters, B. 2008. A framework for efficient and composable oblivious transfer. In Proceedings of the Annual International Cryptology Conference (CRYPTO). Lecture Notes in Computer Science Series, vol. 5157, 554--571. Google ScholarDigital Library
- Sahai, A., and Vadhan, S. P. 2003. A complete problem for statistical zero knowledge. J. ACM 50, 2, 196--249. Google ScholarDigital Library
Index Terms
- New Techniques for Noninteractive Zero-Knowledge
Recommendations
Non-interactive zaps and new techniques for NIZK
CRYPTO'06: Proceedings of the 26th annual international conference on Advances in CryptologyIn 2000, Dwork and Naor proved a very surprising result: that there exist “Zaps”, two-round witness-indistinguishable proofs in the plain model without a common reference string, where the Verifier asks a single question and the Prover sends back a ...
Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES
Verifiably encrypted signatures (VES) are encrypted signatures under a public key of a trusted third party. We can verify their validity without decryption. VES has useful applications such as online contract signing and optimistic fair exchange. We ...
Efficient structure-preserving signature scheme from standard assumptions
SCN'12: Proceedings of the 8th international conference on Security and Cryptography for NetworksWe present an efficient signature scheme that facilitates Groth-Sahai proofs [25] of knowledge of a message, a verification key, and a valid signature on the message, without the need to reveal any of them. Such schemes are called structure-preserving. ...
Comments