Concurrent zero-knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Concurrent zero-knowledge

Full text

Pdf (317 KB)

Source

Journal of the ACM (JACM) archive
Volume 51 , Issue 6 (November 2004) table of contents

Pages: 851 - 898

Year of Publication: 2004

ISSN:0004-5411

Authors

Cynthia Dwork	Microsoft Research SVC, Mountain View, California
Moni Naor	Weizmann Institute of Science, Rehovot, Israel
Amit Sahai	University of California, Los Angeles, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 144, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1039488.1039489 What is a DOI?

ABSTRACT

Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto. In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (α, β) timing constraint: for any two processors P₁ and P₂, if P₁ measures α elapsed time on its local clock and P₂ measures β elapsed time on its local clock, and P₂ starts after P₁ does, then P₂ will finish after P₁ does. We show that if the adversary is constrained by an (α, β) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP. We also address the more specific problem of Deniable Authentication, for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing, that is, in the standard model.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Agrawal, M., Kayal, N., and Saxena, N. 2002. Primes is in P. Manuscript.
	2	Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
	3	B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
	4	M. Bellare , S. Goldwasser, Encapsulated Key Escrow, Massachusetts Institute of Technology, Cambridge, MA, 1996
	5	Bellare, M., Jakobsson, M., and Yung, M. 1997. Round-optimal zero-knowledge arguments based on any one-way function. In Advances in Cryptology---EUROCRYPT '97 Proceedings. Lecture Notes in Computer Science, vol. 1233. Springer-Verlag, New York, pp. 280--305.
	6	Bellare, M., and Yung, M. 1996. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology 9, 3, 149--166.
	7	Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
	8	Thomas Beth , Yvo Desmedt, Identification Tokens - or: Solving the Chess Grandmaster Problem, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.169-177, August 11-15, 1990
	9	Blum, M. 1982. Coin flipping by telephone: A protocol for solving impossible problems. In Advances in Cryptology: A Report on CRYPTO 81 (August 24--26). Department of Electrical and Computer Engineering, U. C. Santa Barbara, ECE Report 82-04. pp. 11--15.
	10	Blum, M. 1986. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians (Berkeley, Calif.). pp. 1444--1451.
	11	Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
	12	Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
	13	Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
	14	Stefan Brands , David Chaum, Distance-bounding protocols, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.344-359, January 1994, Lofthus, Norway
	15	Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
	16	Gilles Brassard , Claude Crépeau , Moti Yung, Constant-round perfect zero-knowledge computationally convincing protocols, Theoretical Computer Science, v.84 n.1, p.23-52, July 22, 1991 [doi>10.1016/0304-3975(91)90259-5]
	17	R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
	18	Ran Canetti , Cynthia Dwork , Moni Naor , Rafail Ostrovsky, Deniable Encryption, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.90-104, August 17-21, 1997
	19	Ran Canetti , Oded Goldreich , Shafi Goldwasser , Silvio Micali, Resettable zero-knowledge (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.235-244, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335334]
	20	Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds, SIAM Journal on Computing, v.32 n.1, p.1-47, 2003 [doi>10.1137/S0097539701392949]
	21	David Chaum , Hans van Antwerpen, Undeniable signatures, Proceedings on Advances in cryptology, p.212-216, July 1989, Santa Barbara, California, United States
	22	David Chaum , Eugène van Heijst , Birgit Pfitzmann, Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 11-15, 1991
	23	Ronald Cramer , Ivan Damgård, New Generation of Secure and Practical RSA-Based Signatures, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.173-185, August 18-22, 1996
	24	Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
	25	Damgård, I. 2000. Efficient concurrent zero-knowledge in the auxiliary string model. In Advances in Cryptology---EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807. Springer, pp. 418--430.
	26	Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276722]
	27	Giovanni Di Crescenzo , Rafail Ostrovsky, On Concurrent Zero-Knowledge with Pre-processing, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.485-502, August 15-19, 1999
	28	Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
	29	Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
	30	Dwork, C., and Naor, M. 1996. Method for message authentication from non-malleable crypto systems. US Patent No. 05539826, issued Aug. 29th 1996.
	31	Dwork, C., and Naor, M. 1998. An efficient existentially unforgeable signature scheme and its applications. J. Crypt., 11, 187--208.
	32	C. Dwork , M. Naor, Zaps and their applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.283, November 12-14, 2000
	33	Cynthia Dwork , Moni Naor , Omer Reingold , Larry Stockmeyer, Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998, Journal of the ACM (JACM), v.50 n.6, p.852-921, November 2003 [doi>10.1145/950620.950623]
	34	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
	35	Cynthia Dwork , Amit Sahai, Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.442-457, August 23-27, 1998
	36	Dwork, C., Shaltiel, R., Smith, A., and Trevisan, L. 2003. An analysis of a two-round zero-knowledge protocol. In Proceedings of the 1st Theory of Cryptography Conference. Springer-Verlag, New York, pp. 101--120.
	37	Cynthia Dwork , Larry Stockmeyer, 2-round zero knowledge and proof auditors, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509958]
	38	Feige, U. 1990. Alternative models for zero knowledge interactive proofs. Ph.D. dissertation, Weizmann Institute of Science, Rehovot, Israel.
	39	U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
	40	U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
	41	Uriel Feige , Adi Shamir, Zero knowledge proofs of knowledge in two rounds, Proceedings on Advances in cryptology, p.526-544, July 1989, Santa Barbara, California, United States
	42	Feige, U., Lapidot, D., and Shamir, A. 1990. Multiple non-interactive zero-knowledge proofs based on a single random string. In Proceedings of 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 308--317.
	43	Rosario Gennaro , Hugo Krawczyk , Tal Rabin, RSA-Based Undeniable Signatures, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.132-149, August 17-21, 1997
	44	Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
	45	Oded Goldreich, Concurrent zero-knowledge with timing, revisited, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509959]
	46	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	47	Goldreich, O., Goldwasser, S., and Micali, S. 1999. Interleaved zero-knowledge in the public-key model, theory of cryptography library, Record 99-15, July. (Available: verb+http:// philby.ucsd.edu/1999.html.)
	48	Goldreich, O., and Kahan, A. 1996. How to construct constant-round zero-knowledge proof systems for NP. J. Crypt. 9, 3, 167--190.
	49	Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
	50	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	51	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	52	Goldreich, O., and Oren, Y. 1994. Definitions and properties of zero-knowledge proof systems. J. Crypt. 7, 1 (Winter), 1--32.
	53	Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.59-68, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185349]
	54	Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28 (Apr.), 270--299.
	55	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	56	Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
	57	Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
	58	Katz, J. 2003. Efficient and non-malleable proofs of plaintext knowledge and applications. In Advances in Cryptology---EUROCRYPT'2003. Lecture Notes in Computer Science, vol. 2656. Springer-Verlag, New York, pp. 211--228.
	59	Kilian, J., and Petrank, E. 1998. An efficient non-interactive zero-knowledge proof system for NP with general assumptions. J. Crypt. 11, 1, 1--27.
	60	Joe Kilian , Erez Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.560-569, July 2001, Hersonissos, Greece [doi>10.1145/380752.380851]
	61	Joe Kilian , Erez Petrank , Charles Rackoff, Lower Bounds for Zero Knowledge on the Internet, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.484, November 08-11, 1998
	62	Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
	63	Krawczyk, H., and Rabin, T. 2000. Chameleon hashing signatures. In Proceedings of Network and Distributed Systems Security Symposium (NDSS). Internet Society, pp. 143--154.
	64	Naor, M. 1991. Bit commitment using pseudo-randomness. J. Crypt. 4, 151--158.
	65	Moni Naor, Deniable Ring Authentication, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.481-498, August 18-22, 2002
	66	Manoj Prabhakaran , Alon Rosen , Amit Sahai, Concurrent Zero Knowledge with Logarithmic Round-Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.366-375, November 16-19, 2002
	67	Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
	68	Richardson, R., and Kilian, J. 1999. On the concurrent composition of zero-knowledge proofs. In Advances in Cryptology---EUROCRYPT '99. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, New York, pp. 415--431.
	69	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	70	R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
	71	Alon Rosen, A Note on the Round-Complexity of Concurrent Zero-Knowledge, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.451-468, August 20-24, 2000
	72	Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999

CITED BY 5

	Yael Tauman Kalai , Yehuda Lindell , Manoj Prabhakaran, Concurrent general composition of secure protocols in the timing model, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Mario Di Raimondo , Rosario Gennaro , Hugo Krawczyk, Deniable authentication and key exchange, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
	Eyal Kushilevitz , Yehuda Lindell , Tal Rabin, Information-theoretically secure protocols and security under composition, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ting-Yi Chang, A Convertible Multi-Authenticated Encryption scheme for group communications, Information Sciences: an International Journal, v.178 n.17, p.3426-3434, September, 2008
	Joseph Y. Halpern , Rafael Pass , Vasumathi Raman, An epistemic characterization of zero knowledge, Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, July 06-08, 2009, California