Concurrent zero-knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Concurrent zero-knowledge

Full text

Pdf (1.54 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 409 - 418

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Cynthia Dwork	IBM Research Division, Almaden Research Center, 650 Harry Road, San Jose, CA
Moni Naor	Dept. of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot 76100, Israel
Amit Sahai	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 30, Citation Count: 36

Additional Information:

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/276698.276853 What is a DOI?

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	M. Bellare , S. Goldwasser, Encapsulated Key Escrow, Massachusetts Institute of Technology, Cambridge, MA, 1996
	2	M. Bellare, R. Irnpagliazzo, and M. Jakobsson, private cornmurdcation
	3	M. Benare, M. Jakobsson and M. Yung. Round-optimal zero-knowledge arguments based on any one-way function. Advances in Cryptology- Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fum~ cd, Springer- Verlag, 1997.
	4	Mihir Bellare , Phillip Rogaway, Provably secure session key distribution: the three party case, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.57-66, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225084]
	5	M. Bellare and M. Yung. Certifying permutations: Noninteractive zero-~owledge ~ased on any trapdoor permutation, Journal of Cryptology, 9(3):149-166, 1998.
	6	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]
	7	M. Blum. Coin flipping by telephone: A protocol .for solving impossible problems. In Allen Gersho, editor, Advances in Cryptology: A Report on CRYPTO 81, pages 11-15, 24-26 August 1981. Department of Electrical and Computer Engineering, U. C. Santa Barbara, ECE Report 82-04, 1982.
	8	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]
	9	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]
	10	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]
	11	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
	12	David Chaum , Hans van Antwerpen, Undeniable signatures, Proceedings on Advances in cryptology, p.212-216, July 1989, Santa Barbara, California, United States
	13	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
	14	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
	15	R. Cramer and V. Shoup A Practical Public Key Cryptosystara Provably Secure against Adaptive Chosen Ciphertez't Attack, private communication, 1998.
	16	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
	17	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
	18	C. Dwork and M. Naor, Method .for message authentication from non. malleable erypto systems, US Patent No. 05539826, issued Aug. 29th 1996.
	19	Cynthia Dwork , Moni Naor, An Efficient Existentially Unforgeable Signature Scheme and its Applications, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.234-246, August 21-25, 1994
	20	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]
	21	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]
	22	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]
	23	U. Feige, D. Lapidot and A. Shamir, Multiple Non- Interactive Zero-Knowledge Proofs Based on a Single Random String, Proceedings of 31st Symposium on Found.~tions of Computer Science, 1990, pp. 308-317.
	24	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
	25	O. Goldreich, Foundations of Cryptography (Fragments of a Book), 1995. Electronic publication: http://www.eccc.urdt rier'de/eccc/inf~/ECCC'B~~ks/eccc'b~~ks'html (Electronic Colloquium on Computational Complexity).
	26	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]
	27	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]
	28	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]
	29	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]
	30	S. Goldwasser and S. Micali. Probabillstie Encryption, Journal of Computer and System Sciences, Vol. 28, April 1984, pp. 270-299.
	31	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]
	32	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]
	33	J. Kilian and E. Petrank, An Efficient Non-Interactive Zero-Knowledge Proof System Jot NP with General Assumptions, Ellectronic Colloquium on Computational Complexity (ECCC)(038), 1995
	34	J. Kilian and E. Petrank, personal communication, 1997'
	35	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
	36	H. Krawczyk and T. Rabin, Chameleon Hashing Signatures, manuscript
	37	M. Naor, Bit Commitment Using Pseudo.Randomness, Journal of Crypto}ogy, vol 4, 1991, pp. 151-158.
	38	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
	39	R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
	40	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]

CITED BY 36

	Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Johan Håstad , Jakob Jonsson , Ari Juels , Moti Yung, Funkspiel schemes: an alternative to conventional tamper resistance, Proceedings of the 7th ACM conference on Computer and communications security, p.125-133, November 01-04, 2000, Athens, Greece
	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
	Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.570-579, July 2001, Hersonissos, Greece
	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
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, Sequential composition of protocols without simultaneous termination, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Yehuda Lindell, Bounded-concurrent secure two-party computation without setup assumptions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	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
	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
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Yair Frankel , Philip MacKenzie , Moti Yung, Adaptively secure distributed public-key systems, Theoretical Computer Science, v.287 n.2, p.535-561, 28 September 2002
	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004
	Ammar Alkassar , Christian Stüble , Ahmad-Reza Sadeghi, Secure object identification: or: solving the Chess Grandmaster Problem, Proceedings of the 2003 workshop on New security paradigms, August 18-21, 2003, Ascona, Switzerland
	Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ya-Fan Chang , Chin-Chen Chang , Chia-Lin Kao, An improvement on a deniable authentication protocol, ACM SIGOPS Operating Systems Review, v.38 n.3, p.65-74, July 2004
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated byzantine agreement, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Manoj Prabhakaran , Amit Sahai, New notions of security: achieving universal composability without trusted setup, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Mario Di Raimondo , Rosario Gennaro, New approaches for deniable authentication, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Mario Di Raimondo , Rosario Gennaro , Hugo Krawczyk, Secure off-the-record messaging, Proceedings of the 2005 ACM workshop on Privacy in the electronic society, November 07-07, 2005, Alexandria, VA, USA
	Boaz Barak , Yehuda Lindell , Salil Vadhan, Lower bounds for non-black-box zero knowledge, Journal of Computer and System Sciences, v.72 n.2, p.321-391, March 2006
	Boaz Barak , Yehuda Lindell, Strict polynomial-time in simulation and extraction, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Chun-Ta Li , Min-Shiang Hwang , Chi-Yu Liu, An electronic voting protocol with deniable authentication for mobile ad hoc networks, Computer Communications, v.31 n.10, p.2534-2540, June, 2008
	Yunlei Zhao, A note on the Dwork-Naor timed deniable authentication, Information Processing Letters, v.100 n.1, p.1-7, 16 October 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Silvio Micali , Rafael Pass, Local zero knowledge, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Wei-Bin Lee , Chia-Chun Wu , Woei-Jiunn Tsaur, A novel deniable authentication protocol using generalized ElGamal signature scheme, Information Sciences: an International Journal, v.177 n.6, p.1376-1381, March, 2007
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated Byzantine Agreement, Journal of the ACM (JACM), v.53 n.6, p.881-917, November 2006
	Sergio Rajsbaum, ACM SIGACT news distributed computing column 24, ACM SIGACT News, v.37 n.4, December 2006
	Dario Catalano , Ivan Visconti, Hybrid commitments and their applications to zero-knowledge proof systems, Theoretical Computer Science, v.374 n.1-3, p.229-260, April, 2007
	Qiong Ren , Yi Mu , Willy Susilo, Mitigating phishing with ID-based online/offline authentication, Proceedings of the sixth Australasian conference on Information security, January 01-01, 2008, Wollongong, NSW, Australia
	Rongxing Lu , Zhenfu Cao , Shengbao Wang , Haiyong Bao, A New ID-Based Deniable Authentication Protocol, Informatica, v.18 n.1, p.67-78, January 2007
	Bin Wang , ZhaoXia Song, A non-interactive deniable authentication scheme based on designated verifier proofs, Information Sciences: an International Journal, v.179 n.6, p.858-865, March, 2009
	Huijia Lin , Rafael Pass , Muthuramakrishnan Venkitasubramaniam, A unified framework for concurrent security: universal composability from stand-alone non-malleability, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA