Salil Vadhan
- 1.V. Arvind and J. KObler. On resource-bounded measure and pseudorandomness. In Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 235-249. LNCS 1346, Springer-Verlag, 1997. Google Scholar
Digital Library
- 2.L. Babai and S. Moran. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36:254--276, 1988. Google ScholarDigital Library
- 3.M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM J. Comput., 23(1):97-119, Feb. 1994. Google ScholarDigital Library
- 4.M. Bellare, S. Micali, and R. Ostrovsky. The (tree) complexity of statistical zero knowledge. In Proceedings of the Twenty Second Annual A CM Symposium on Theory of Computing, pages 494--502, Baltimore, Maryland, 14--16 May 1990. Google ScholarDigital Library
- 5.M. Ben-Or, O. Goldreich, S. Goldwasser, J. HSstad, J. Kilian, S. Micali, and P. Rogaway. Everything provable is provable in zero-knowledge. In S. Goldwasser, editor, Advances in CryptologymCRYPTO '88, volume 403 of Lecture Notes in Computer Science, pages 37-56. Springer-Verlag, 1990, 21-25 Aug. 1988. Google ScholarDigital Library
- 6.M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 113-131, Chicago, Illinois, 2--4 May 1988. Google ScholarDigital Library
- 7.R. B. Boppana, J. H~tstad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:127-132, 1987. Google ScholarDigital Library
- 8.P. Bro Miltersen and N. Vinodchandran. Derandomizing Arthur-Merlin games using hitting sets. In 40th Annual Symposium on Foundations of Computer Sciencd, New York, NY, 17-19 Oct. 1999. IEEE. Google ScholarDigital Library
- 9.I. Damgtrd, O. Goldreich, T. Okamoto, and A. Wigderson. Honest verifier vs. dishonest verifier in public coin zero-knowledge proofs. In Proceedings of Crypto '95, Lecture Notes in Computer Science, volume 403. Springer-Verlag, 1995. Google ScholarDigital Library
- 10.S. Even, A. L. Selman, and Y. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159--173, May 1984. Google ScholarDigital Library
- 11.M. Fiirer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos. On completeness and soundness in interactive proof systems. In S. Micali, editor, Advances in Computing Research, volume 5, pages 429--442. JAC Press, Inc., 1989.Google Scholar
- 12.O. Golclreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, Oct. 1986. Google ScholarDigital Library
- 13.O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. A CM, 38(1 ):691-729, 1991. Google ScholarDigital Library
- 14.O. Goldreich, A. Sahai, and S. Vadhan. Honest verifier statistical zero-knowledge equals general statistical zero-knowledge, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 399-408, Dallas, 23-26 May 1998. Google ScholarDigital Library
- 15.O. Goldreich and S. Vadhan. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 54-73, Atlanta, GA, May 1999. IEEE Computer Society Press. Google ScholarDigital Library
- 16.S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(i): 186--208, February 1989. Google ScholarDigital Library
- 17.S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Advances in Computing Research, volume 5, pages 73-90. JAC Press, Inc., 1989.Google Scholar
- 18.J. Hfistad, R. impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4): 1364-1396, August 1999. Google ScholarDigital Library
- 19.R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 44-61, Seattle, Washington, 15-17 May 1989. Google ScholarDigital Library
- 20.R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 220-229, E1 Paso, Texas, 4-6 May 1997. Google ScholarDigital Library
- 21.R. Impagliazzo and M. Yung. Direct minimum-knowledge computations (extended abstract). In C. Pomerance, editor, Advances in Cryptology--CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 40--51. Springer-Vefiag, 1988, 16--20 Aug. 1987. Google ScholarDigital Library
- 22.J. Kilian. Achieving zero-knowledge robustly. In A. J. Menezes and S. A. Vanstone, editors, Advances in Cryptology~CRYPTO '90, volume 537 of Lecture Notes in Computer Science, pages 313-325. Springer-Verlag, 1991, 1 I-15 Aug. 1990. Google ScholarDigital Library
- 23.A. R. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the Thirty-first Annual A CM Symposium on Theory of Computing, pages 659--667, Atlanta, 1-4 May 1999. Google ScholarDigital Library
- 24.M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput., 17(2):373-386, Apr. 1988. Google ScholarDigital Library
- 25.C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, Oct. 1992. Google ScholarDigital Library
- 26.M. Naor and O. Reingold. On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract). In Proceedings of the Twenty-Ninth Annual A CM Symposium on Theory of Computing, pages 189-199, E1 Paso, Texas, 4-6 May 1997. Google ScholarDigital Library
- 27.N. Nisan and A. Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, Oct. 1994. Google ScholarDigital Library
- 28.T. Okamoto. On relationships between statistical zero-knowledge proofs. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 649-658, Philadelphia, Pennsylvania, 22-24 May 1996. See also preprint of full version, Oct. 1997. Google ScholarDigital Library
- 29.R. Ostrovsky, R. Venkatesan, and M. Yung. Interactive hashing simplifies zero-knowledge protocol design. In Proceedings of Eurocrypt '93, Lecture Notes in Computer Science. Springer-Verlag, 1993. Google ScholarDigital Library
- 30.A. Sahai and S. P. Vadhan. A complete promise problem for statistical zero-knowledge. In 38th Annual Symposium on Foundations of Computer Science, pages 448--457, Miami Beach, Florida, 20-22 Oct. 1997. IEEE. Google ScholarDigital Library
- 31.A. Shamir. IP = PSPACE. J. ACM, 39(4):869-877, Oct. 1992. Google ScholarDigital Library
- 32.S. Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts institute of Technology, August 1999. Google ScholarDigital Library
Index Terms
- On transformation of interactive proofs that preserve the prover's complexity
Recommendations
On interactive proofs with a laconic prover
We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Håstad (1998). Let L be a language that has an interactive proof in which the prover sends few (say b) bits to the verifier. We prove that the ...
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
If every language in coNP has a constant-round interactive proof system, then the polynomial-time hierarchy collapses [R.B. Boppana, J. Håstad, S. Zachos, Does co-NP have short interactive proofs? Information Processing Letters 25 (2) (1987) 127-132]. ...
Generalized quantum arthur-merlin games
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThis paper investigates the role of interaction and coins in quantum Arthur-Merlin games(also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum ...
Comments