Strict polynomial-time in simulation and extraction. (English) Zbl 1192.68343
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 484-493, electronic only (2002).
For the entire collection see [Zbl 1074.68502].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | B. Barak. How to go beyond the black-box simulation barrier. Proc. of the 42nd FOCS, 2001.]] |
| [2] | B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell. Resettably-sound zero-knowledge and its applications. In 42nd FOCS, 2001. Full version in Cryptology ePrint Archive, Record 2001/063, 2001.]] |
| [3] | M. Bellare and O. Goldreich. On defining proofs of knowledge. In CRYPTO’92, Springer-Verlag (LNCS 740), pages 390-420, 1992.]] · Zbl 0823.94016 |
| [4] | M. Blum. Coin flipping by phone. In The 24th IEEE Computer Conference, pages 133-137, 1982.]] |
| [5] | G. Brassard, C. Crépeau, and M. Yung. Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds. In EUROCRYPT’89, 1989.]] |
| [6] | R. Canetti, O. Goldreich, S. Goldwasser and S. Micali. Resettable zero-knowledge. In 32nd STOC, 2000. Full version in Cryptology ePrint Archive, Report 1999/022, 1999.]] 10.1145/335305.335334 |
| [7] | C. Dwork, M. Naor, and A. Sahai. Concurrent zero knowledge. In Proceedings of the 30th STOC, 1998.]] 10.1145/276698.276853 |
| [8] | Feige, Lapidot, and Shamir. Multiple noninteractive zero knowledge proofs under general assumptions. SICOMP: SIAM Journal on Computing, 29, 1999.]] 10.1137/S0097539792230010 · Zbl 1018.94015 |
| [9] | U. Feige. Alternative Models for Zero Knowledge Interactive Proofs. PhD thesis, Dept. of Computer Science, Weizmann Institute of Science, Israel, 1990.]] |
| [10] | U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Jour. of Crypto., 1(2):77-94, 1988.]] 10.1007/BF02351717 · Zbl 0659.94006 |
| [11] | U. Feige and A. Shamir. Zero knowledge proofs of knowledge in two rounds. In CRYPTO’89, 1989.]] · Zbl 0722.68045 |
| [12] | U. Feige and A. Shamir. Witness indistinguishable and witness hiding protocols. In 22nd STOC, 1990.]] 10.1145/100216.100272 |
| [13] | Goldreich. Notes on levin’s theory of average-case complexity. In ECCR Technical Reports, 1997.]] |
| [14] | O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001.]] · Zbl 1007.94016 |
| [15] | O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167-189, 1996.]] · Zbl 0855.68085 |
| [16] | O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. In JACM, 38(3):691-729, July 1991.]] 10.1145/116825.116852 · Zbl 0799.68101 |
| [17] | S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In 17th STOC, pages 291-304, 1985.]] 10.1145/22145.22178 · Zbl 0900.94025 |
| [18] | S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989.]] 10.1137/0218012 · Zbl 0677.68062 |
| [19] | L. A. Levin. Average case complete problems. SIAM Journal on Computing, 15(1):285-286, 1986.]] 10.1137/0215020 · Zbl 0589.68032 |
| [20] | Y. Lindell. Parallel coin-tossing and constant-round secure two-party computation. In CRYPTO 2001. Full version in Cryptology ePrint Archive, 2001/107, 2001.]] |
| [21] | M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151-158, 1991.]] · Zbl 0731.68033 |
| [22] | R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. Technical Report TR-93-073, International Computer Science Institute, Berkeley, CA, Nov. 1993.]] |
| [23] | M. Tompa and H. Woll. Random self-reducibility and zero-knowledge interactive proofs of possession of information. In Proc. of 28th FOCS, 1987.]] |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
