Local zero knowledge

ABSTRACT

We put forward the notion of Local Zero Knowledge and provide its first implementations in a variety of settings under standard complexity assumptions.Whereas the classical notion of Zero Knowledge guarantees the secrecy only of information that is hard to compute, the new one meaningfully guarantees the secrecy of any information (in case of perfect zero-knowledge, and asymptotically in all other cases). Consequently, Local Zero Knowledge remains very meaningful even if DP = NP.

REFERENCES

• 1: 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
• 2: Boaz Barak , Oded Goldreich, Universal Arguments and their Applications, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.194, May 21-24, 2002
• 3: 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 [doi>10.1145/509907.509979]
• 4: M. Blum. How to prove a Theorem So No One Else Can Claim It. Proc. of the International Congress of Mathematicians, Berkeley, California, USA, pages 1444--1451, 1986.
• 5: 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]
• 6: 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]
• 7: R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 34th STOC, pages 494--503, 2002.
• 8: David Chaum , Hans Van Antwerpen, Undeniable Signatures, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.212-216, August 20-24, 1989
• 9: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 10: Yevgeniy Dodis , Silvio Micali, Parallel Reducibility for Information-Theoretically Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.74-92, August 20-24, 2000
• 11: 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]
• 12: M. Fischer, S. Micali, and C. Rackoff. A Secure Protocol for the Oblivious Transfer. Journal of Cryptology, 9(3): 191--195, 1996.
• 13: 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]
• 14: Uriel Feige , Adi Shamir, Zero Knowledge Proofs of Knowledge in Two Rounds, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.526-544, August 20-24, 1989
• 15: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 16: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 17: O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. Jour. of Cryptology, Vol. 9, No. 2, pages 167--189, 1996.
• 18: 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]
• 19: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 20: 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]
• 21: 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]
• 22: S. Halevi and S. Micali. Conservative Proofs of Knowledge. MIT/LCS/TM-578, May 1998.
• 23: 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]
• 24: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 25: Yehuda Lindell, Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.171-189, August 19-23, 2001
• 26: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 27: D. Micciancio, S. Vadhan. Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In Crypto03. Springer LNCS 2729, pages. 282--298, 2003.
• 28: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 29: M. Naor. Bit Commitment using Pseudorandomness. Jour. of Cryptology, Vol. 4, pages 151--158, 1991.
• 30: R. Pass. Simulation in Quasi-polynomial Time and its Application to Protocol Composition. In EuroCrypt03, Springer LNCS 2656, pages 160--176, 2003.
• 31: Rafael Pass , Alon Rosen, New and improved constructions of non-malleable cryptographic protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060670]
• 32: 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
• 33: R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In EuroCrypt99, Springer LNCS 1592, pages 415--431, 1999.
• 34: Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March 2003 [doi>10.1145/636865.636868]
• 35: M. Tompa, H. Woll. Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information. In 28th FOCS, pages 472--482, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Theory

Keywords:
cryptography, zero knowledge