A language-dependent cryptographic primitive

1. Aiello, W., and Håstad, J., Statistical Zero-Knowledge Languages Can Be Recognized in Two Rounds,J. Comput. System Sci., Vol. 42, No. 3, pp. 327–345 (1991).

   Article  MATH  MathSciNet  Google Scholar 

2. Bellare, M., Micali, S., and Ostrovsky, R., Perfect Zero-Knowledge in Constant Rounds,Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, pp. 482–493 (1990).

3. Bellare, M., Micali, S., and Ostrovsky, R., The (True) Complexity of Statistical Zero-Knowledge,Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, pp. 494–502 (1990).

4. Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., and Rogaway, P., Everything Provable Is Provable in Zero-Knowledge.Proceedings of Crypto '88, Lecture Notes in Computer Science, Vol. 403, pp. 37–56 (1990).

   Google Scholar 

5. Blum, M., How To Prove a Theorem so No One Else Can Claim It,Proceedings of the ICM, pp. 1444–1451 (1986).

6. Boppana, R., Håstad, J., and Zachos, S., Does co-NP Have Short Interactive Proofs?,Inform. Process. Lett., Vol. 25, No. 2, pp. 127–132 (1987).

   Article  MATH  MathSciNet  Google Scholar 

7. Boyar, J., Friedl, K., and Lund, C., Practical Zero-Knowledge Proof: Giving Hints and Using Deficiencies,J. Cryptology, Vol. 4, No. 3, pp. 185–206 (1991).

   Article  MATH  MathSciNet  Google Scholar 

8. Brassard, G., Chaum, D., and Crépeau, C., Minimum Disclosure Proofs of Knowledge.J. Comput. System Sci., Vol. 37, No. 2, pp. 156–189 (1988).

   Article  MATH  MathSciNet  Google Scholar 

9. Chang, R., On the Structure of Bounded Queries to ArbitraryNP Sets,Proceedings of the 4th Structure in Complexity Theory Conference, pp. 250–258 (1989).

10. Feige, U., and Shamir, A., Zero-Knowledge Proofs of Knowledge in Two Rounds.Proceedings of Crypto '89. Lecture Notes in Computer Science, Vol. 435, pp. 526–544 (1990).

    MathSciNet  Google Scholar 

11. Fortnow, L., The Complexity of Perfect Zero-Knowledge,Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 204–209 (1987).

12. Goldreich, O., and Krawczyk, H., On the Composition of Zero-Knowledge Proof Systems.Proceedings of ICALP '90, Lecture Notes in Computer Science, Vol. 443, pp. 268–282 (1990).

    Google Scholar 

13. Goldreich, O., Micali, S., and Wigderson, A., Proofs that Yield Nothing but Their Validity or All Languages inNP have Zero-Knowledge Proof Systems.J. Assoc. Comput. Mach., Vol. 38, No. 1, pp. 691–729 (1991).

    MATH  MathSciNet  Google Scholar 

14. Goldreich, O., and Oren, Y., Definitions and Properties of Zero-Knowledge Proof Systems.J. Cryptology, Vol. 7, No. 1, pp. 1–32 (1994).

    MATH  MathSciNet  Google Scholar 

15. Goldreich, O., Ostrovsky, R., and Petrank, E., Computational Complexity and Knowledge Complexity,Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 534–543 (1994).

16. Goldwasser, S., Micali, S., and Rackoff, C., The Knowledge Complexity of Interactive Proof Systems,SIAM J. Comput., Vol. 18, No. 1, pp. 186–208 (1989).

    Article  MATH  MathSciNet  Google Scholar 

17. Köbler, J., Schöning, U., and Torán, J.,The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, Boston (1993).

    MATH  Google Scholar 

18. Lozano, A., and Torán, L., On the Nonuniform Complexity of the Graph Isomorphism Problem,Proceedings of the 7th Structure in Complexity Theory Conference, pp. 118–131 (1992).

19. Naor, M., Ostrovksy, R., Venkatesan, R., and Yung, M., Perfect Zero-Knowledge Arguments forNP Can Be Based on General Complexity Assumptions.Proceedings of Crypto, '92, Lecture Notes in Computer Science, Vol. 740, pp. 196–214 (1993).

    Google Scholar 

20. Ostrovsky, R., Venkatesan, R., and Yung, M., Secure Commitment Against a Powerful Adversary.Proceedings of STACS '92, Lecture Notes in Computer Science, Vol. 577, pp. 439–448 (1992).

    Google Scholar 

21. Tompa, M., and Woll, H., Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information,Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 472–482 (1987).

Download references