ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The knowledge complexity of interactive proof-systems
Full text PdfPdf (1.39 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents
Providence, Rhode Island, United States
Pages: 291 - 304  
Year of Publication: 1985
ISBN:0-89791-151-2
Authors
S Goldwasser  MIT
S Micali  MIT
C Rackoff  University of Toronto
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 24,   Downloads (12 Months): 170,   Citation Count: 78
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/22145.22178
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.

 
B
Babai L., Trading Group Theory for Randomness
 
Bl1
M. Blum, Coin flipp#~g b), telephone, IEEE COMPCON 1982.
 
Bl2
M. Blum, Three applications of the oblivious transfer, Unpublished manuscript, 1981
 
BPT
Berger, Peralta, Tedrick, O, .fixing the Oblivious 'lr ansJkr, Presented In Eurocrypt 1983. These Proceedings
C
Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States  [doi>10.1145/800157.805047]
 
DB
D. Dolev, A. Broder, Flipping Coins in Many Pockets, Proc. of 25th FOCS, 1984.
 
EGL
Even, Goldreich Lempel, ,4 randomized protocol for Signing Contracts, Advances in Cryptology: proceedings of Crypto 1982, Plenum press, 1983, 205-210.
 
FHV
R. Fagin, I. Halpem, M. Vardi, A modeltheoretic analysis of knowledge, Proc. 6f 2$th FOCS, i984.
 
FMR
M. Fischer, S. Micali and C. Rackoff, A Secure Protocol jbr the Oblivious Transfer, Eurocrypt 1984.
HM
Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada  [doi>10.1145/800222.806735]
 
H
J. Hastad, On Solving A System of Simultaneous Mo&lar Polynomial Equations of Low Degree, In preparation.
HR
Joseph Y. Halpern , Michael O. Rabin, A logic to reason about likelihood, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.310-319, December 1983  [doi>10.1145/800061.808760]
 
HS
J. Hastad, A. Shamir, On the Security of Linearly Truncated Sequences, this proceedings.
 
GM
S. Goldwasser, and S. Micali, Probabilistic Encryplion, JCSS Vol. 28, No. 2, April 1984.
 
GM
S. Goldwasser, and S. Mlcali ,Prooj~ with Untrusted Oracles, Unpublished Manuscript 1983.
 
GGM
O. Goldreich, S. Goldwasser, and S. Micali, How to Construct Random l:~nclion, 25th FOCS, 1984.
 
L
L.A.l.evin, Universal Sequential Search Problems, Probl. Inform. l'ransm. 9/3 (1973), pp. 265-266.
 
P
C. Papadimitriou, Games against nature, Proc. 24th ann. Syrup. on Foundations of Computer Science, 1983, pp 446-450.
PS
Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States  [doi>10.1145/800070.802192]
Y
Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States  [doi>10.1145/800135.804414]
 
Y
A.C..Yao, They and A~lications of Trapdoor Functions, Pro~. of 23rd FOCS, 1982.

CITED BY  78
Wei Jiang , Chris Clifton , Murat Kantarcıoğlu, Transforming semi-honest protocols to ensure accountability, Data & Knowledge Engineering, v.65 n.1, p.57-74, April, 2008
Guillaume Poupard , Jacques Stern, On the fly signatures based on factoring, Proceedings of the 6th ACM conference on Computer and communications security, p.37-45, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
Jeffrey Jackson , Andrew Tomkins, A computational model of teaching, Proceedings of the fifth annual workshop on Computational learning theory, p.319-326, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996
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
B. Ravikumar, A note on checking matrix products (extended abstract), Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.937-943, March 1992, Kansas City, Missouri, United States
U. Fiege , A. Fiat , A. Shamir, Zero knowledge proofs of identity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.210-217, January 1987, New York, New York, United States
Ari Juels , Marcus Peinado, Hiding cliques for cryptographic security, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.678-684, January 25-27, 1998, San Francisco, California, United States
Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States
M. Abadi , J. Feigenbaum , J. Kilian, On hiding information from an oracle, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.195-203, January 1987, New York, New York, United States
Sally A. Goldman , H. David Mathias, Teaching a smart learner, Proceedings of the sixth annual conference on Computational learning theory, p.67-76, July 26-28, 1993, Santa Cruz, California, United States
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
Mihir Bellare , Erez Petrank, Making zero-knowledge provers efficient, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.711-722, May 04-06, 1992, Victoria, British Columbia, Canada
M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States
Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada
Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States
L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States
David Pointcheval , Guillaume Poupard, A New \mathcal{NP}-Complete Problem and Public-Key Identification, Designs, Codes and Cryptography, v.28 n.1, p.5-31, January 2003
Anne Condon, Space-bounded probabilistic game automata, Journal of the ACM (JACM), v.38 n.2, p.472-494, April 1991
László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States
M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States
László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States
Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992
Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational complexity and knowledge complexity (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.534-543, May 23-25, 1994, Montreal, Quebec, Canada
Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada
S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States
Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States
Ming-Deh A. Huang , Shang-Hua Teng, Secure and verifiable schemes for election and general distributed computing problems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.182-196, August 15-17, 1988, Toronto, Ontario, Canada
Josh C Benaloh , Moti Yung, Distributing the power of a government to enhance the privacy of voters, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.52-62, August 11-13, 1986, Calgary, Alberta, Canada
Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada
Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
Charles Rackoff , Daniel R. Simon, Cryptographic defense against traffic analysis, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.672-681, May 16-18, 1993, San Diego, California, United States
Jörg Rothe, Some facets of complexity theory and cryptography: A five-lecture tutorial, ACM Computing Surveys (CSUR), v.34 n.4, p.504-549, December 2002
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
Benny Chor , Michael O. Rabin, Achieving independence in logarithmic number of rounds, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.260-268, August 10-12, 1987, Vancouver, British Columbia, Canada
L. Fortnow , M. Sipser, Probabilistic computation and linear time, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.148-156, May 14-17, 1989, Seattle, Washington, United States
Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States
Mike Burmester , Vassilios Chrissikopoulos , Panayiotis Kotzanikolaou , Emmanouil Magkos, Strong forward security, Proceedings of the 16th international conference on Information security: Trusted information: the new decade challenge, June 11-13, 2001, Paris, France
Ingrid Biehl , Sacher Paulus , Tsuyoshi Takagi, Efficient Undeniable Signature Schemes Based on Ideal Arithmetic in Quadratic Orders, Designs, Codes and Cryptography, v.31 n.2, p.99-123, February 2004
Silvio Micali, Knowledge and efficient computation, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000
Ronald Fagin , Joseph Y. Halpern, Reasoning about knowledge and probability, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
Martin Tompa, Zero knowledge interactive proofs of knowledge (a digest), Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
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
Paul F. Syverson, An epistemic logic of situations: extended abstract, Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge, p.109-121, March 13-16, 1994, Pacific Grove, California
Ning Chen , Jia-Wei Rong, Memorizable interactive proof and zero-knowledge proof systems, Journal of Computer Science and Technology, v.19 n.6, p.936-941, November 2004
Jaideep Vaidya , Chris Clifton, Privacy-Preserving Data Mining: Why, How, and When, IEEE Security and Privacy, v.2 n.6, p.19-27, November 2004
Yoram Moses, Resource-bounded knowledge, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
Michael Backes , Jan Camenisch , Dieter Sommer, Anonymous yet accountable access control, Proceedings of the 2005 ACM workshop on Privacy in the electronic society, November 07-07, 2005, Alexandria, VA, USA
Joseph Y. Halpern, Reasoning about knowledge: an overview, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
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
Steve R. White , Liam Comerford, ABYSS: An Architecture for Software Protection, IEEE Transactions on Software Engineering, v.16 n.6, p.619-629, June 1990
Gilles Brassard, How convincing is your protocol?, ACM SIGACT News, v.22 n.1, p.5-12, Winter 1991
John Watrous, Zero-knowledge against quantum attacks, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States
Hervé Sibert , Patrick Dehornoy , Marc Girault, Entity authentication schemes using braid word reduction, Discrete Applied Mathematics, v.154 n.2, p.420-436, 1 February 2006
Roberto Zunino , Pierpaolo Degano, Weakening the perfect encryption assumption in Dolev-Yao adversaries, Theoretical Computer Science, v.340 n.1, p.154-178, 13 June 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
Jeffrey C. Mogul , Martin Arlitt, SC2D: an alternative to trace anonymization, Proceedings of the 2006 SIGCOMM workshop on Mining network data, p.323-328, September 11-15, 2006, Pisa, Italy
Josh Benaloh, Simple verifiable elections, Proceedings of the USENIX/Accurate Electronic Voting Technology Workshop 2006 on Electronic Voting Technology Workshop, p.5-5, August 01, 2006, Vancouver, B.C., Canada
A. Pavan , Alan L. Selman , Samik Sengupta , N. V. Vinodchandran, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Theoretical Computer Science, v.385 n.1-3, p.167-178, October, 2007
Bala Ravikumar, On some variations of two-way probabilistic finite automata models, Theoretical Computer Science, v.376 n.1-2, p.127-136, May, 2007
Véronique Cortier , Stéphanie Delaune , Pascal Lafourcade, A survey of algebraic properties used in cryptographic protocols, Journal of Computer Security, v.14 n.1, p.1-43, January 2006
Rafael Pass , Muthuramakrishnan Venkitasubramaniam, An efficient parallel repetition theorem for Arthur-Merlin games, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Wei Jiang , Chris Clifton, A secure distributed framework for achieving k-anonymity, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.4, p.316-333, November 2006
Gregory Conti, Googling considered harmful, Proceedings of the 2006 workshop on New security paradigms, September 19-22, 2006, Germany
Hirokazu Sasamoto , Nicolas Christin , Eiji Hayashi, Undercover: authentication usable in front of prying eyes, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy
Patrick Traynor , Michael Chien , Scott Weaver , Boniface Hicks , Patrick McDaniel, Noninvasive Methods for Host Certification, ACM Transactions on Information and System Security (TISSEC), v.11 n.3, p.1-23, March 2008
Haowen Chan , Adrian Perrig , Bartosz Przydatek , Dawn Song, SIA: Secure information aggregation in sensor networks, Journal of Computer Security, v.15 n.1, p.69-102, January 2007
Sławomir Grzonkowski , Wojciech Zaremba , Maciej Zaremba , Bill McDaniel, Extending web applications with a lightweight zero knowledge proof authentication, Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology, October 28-31, 2008, Cergy-Pontoise, France
Danfeng Yao , Keith B. Frikken , Mikhail J. Atallah , Roberto Tamassia, Private Information: To Reveal or not to Reveal, ACM Transactions on Information and System Security (TISSEC), v.12 n.1, p.1-27, October 2008
Cheryl Beaver, Cryptology in the Classroom: Analyzing a Zero-Knowledge Protocol, Cryptologia, v.33 n.1, p.16-23, January 2009
Andrew C. C. Yao , Frances F. Yao , Yunlei Zhao, A note on universal composable zero-knowledge in the common reference string model, Theoretical Computer Science, v.410 n.11, p.1099-1108, March, 2009
Yoshikazu Hanatani , Yuichi Komano , Kazuo Ohta , Noboru Kunihiro, Provably Secure Untraceable Electronic Cash against Insider Attacks, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.980-991, May 2007
Andrew c. c. Yao , Frances f. Yao , Yunlei Zhao, A note on the feasibility of generalised universal composability†, Mathematical Structures in Computer Science, v.19 n.1, p.193-205, February 2009
Ronald Fagin , Joseph Y. Halpern, Belief, awareness, and limited reasoning: preliminary report, Proceedings of the 9th international joint conference on Artificial intelligence, p.491-501, August 18-23, 1985, Los Angeles, California
Mayank Bawa , Roberto J. Bayardo, Jr , Rakesh Agrawal , Jaideep Vaidya, Privacy-preserving indexing of documents on the network, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.4, p.837-856, August 2009

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE


General Terms:
Languages, Theory, Verification

Collaborative Colleagues:
S Goldwasser: colleagues
S Micali: colleagues
C Rackoff: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player