{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:01:10Z","timestamp":1725494470766},"publisher-location":"New York, NY","reference-count":21,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9780387973173"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/0-387-34805-0_45","type":"book-chapter","created":{"date-parts":[[2007,11,9]],"date-time":"2007-11-09T02:05:53Z","timestamp":1194573953000},"page":"507-525","source":"Crossref","is-referenced-by-count":5,"title":["On the concrete complexity of zero-knowledge proofs"],"prefix":"10.1007","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[]},{"given":"Ren\u00e9","family":"Peralta","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","series-title":"Lect Notes Comput Sci","first-page":"213","volume-title":"Advances in Cryptology-proceedings of CRYPTO 86","author":"J. C. Benaloh","year":"1987","unstructured":"J. C. Benaloh. Cryptographic capsules: A disjunctive primitive for interactive protocols. In Advances in Cryptology-proceedings of CRYPTO 86, Lecture Notes in Computer Science, pages 213\u2013222 Springer-Verlag, 1987."},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan. Designing programs that check their work. Proceedings of the 21th Annual ACM Symposium on the Theory of Computing, pages 86\u201397, 1989.","DOI":"10.1145\/73007.73015"},{"key":"45_CR3","unstructured":"J. Boyar, M. Krentel, and S. Kurtz. A discrete logarithm implementation of zero-knowledge blobs. Technical Report 87-002, University of Chicago, 1987. To appear in Journal of Cryptology."},{"key":"45_CR4","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"G. Brassard, D. Chaum, and C. Cr\u00e9peau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37:156\u2013189, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"G. Brassard and C. Cr\u00e9peau. Nontransitive transfer of confidence: a perfect zero-knowledge interactive protocol for Sat and beyond. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science, pages 188\u2013195, 1986.","DOI":"10.1109\/SFCS.1986.33"},{"key":"45_CR6","series-title":"Lect Notes Comput Sci","first-page":"223","volume-title":"Advances in Cryptology-proceedings of CRYPTO 86","author":"G. Brassard","year":"1987","unstructured":"G. Brassard and C. Cr\u00e9peau. Zero-knowledge simulation of boolean circuits. In Advances in Cryptology-proceedings of CRYPTO 86, Lecture Notes in Computer Science, pages 223\u2013233. Springer-Verlag, 1987."},{"key":"45_CR7","series-title":"Lect Notes Comput Sci","first-page":"195","volume-title":"Advances in Cryptology-proceedings of CRYPTO 86","author":"D. Chaum","year":"1987","unstructured":"D. Chaum. Demonstrating that a public predicate can be satisfied without revealing any information about how. In Advances in Cryptology-proceedings of CRYPTO 86, Lecture Notes in Computer Science, pages 195\u2013199. Springer-Verlag, 1987."},{"key":"45_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/3-540-48184-2_7","volume-title":"Advances in Cryptology-proceedings of CRYPTO 87","author":"D. Chaum","year":"1988","unstructured":"D. Chaum, I. Damg\u00e5rd, and J. van de Graaf. Multiparty computations ensuring privacy of each party\u2019s input and correctness of the result. In Advances in Cryptology-proceedings of CRYPTO 87, Lecture Notes in Computer Science, pages 87\u2013119. Springer-Verlag, 1988."},{"issue":"17","key":"45_CR9","first-page":"366","volume":"I","author":"P.L. Chebyshev","year":"1852","unstructured":"P.L. Chebyshev. M\u00e9moire sur les nombres premiers. J. Math. Pures et Appl, (I)(17):366\u2013390, 1852.","journal-title":"J. Math. Pures et Appl"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"45_CR11","series-title":"Lect Notes Comput Sci","volume-title":"Advances in Cryptology-proceedings of EUROCRYPT 89","author":"B. Boer den","year":"1989","unstructured":"B. den Boer. An efficiency improvement to prove satisfiability with zero knowledge with public key. In Advances in Cryptology-proceedings of EUROCRYPT 89, Lecture Notes in Computer Science, 1989. To appear."},{"issue":"2","key":"45_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF02351717","volume":"1","author":"U. Feige","year":"1988","unstructured":"U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77\u201394,1988.","journal-title":"Journal of Cryptology"},{"key":"45_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1:237\u2013267, 1976.","journal-title":"Theoretical Computer Science"},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In 27th. IEEE Symposium on Foundations of Computer Science, pages 174\u2013187, 1986.","DOI":"10.1109\/SFCS.1986.47"},{"key":"45_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28:270\u2013299, 1984.","journal-title":"Journal of Computer and System Sciences"},{"issue":"l","key":"45_CR16","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal of Computation, 18(l):186\u2013208, 1989.","journal-title":"SIAM Journal of Computation"},{"key":"45_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-48184-2_4","volume-title":"Advances in Cryptology-proceedings of CRYPTO 87","author":"R. Impagliazzo","year":"1988","unstructured":"R. Impagliazzo and M. Yung. Direct minimum-knowledge computations. In Advances in Cryptology-proceedings of CRYPTO 87, Lecture Notes in Computer Science, pages 40\u201351. Springer-Verlag, 1988."},{"key":"45_CR18","series-title":"Lect Notes Comput Sci","volume-title":"Advances in Cryptology-proceedings of CRYPTO 89","author":"J. Kilian","year":"1990","unstructured":"J. Kilian, S. Micali, and R. Ostrovsky. Efficient zero-knowledge proofs with bounded interaction. In Advances in Cryptology-proceedings of CRYPTO 89, Lecture Notes in Computer Science. Springer-Verlag, 1990. To appear."},{"key":"45_CR19","unstructured":"W. LeVeque. Fundamentals of Number Theory. Addison-Wesley, 1977."},{"key":"45_CR20","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"23","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger and M. Fischer. Relations among complexity measures. Journal of the Association for Computing Machinery, 23:361\u2013381, 1979.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"45_CR21","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J. Rosser","year":"1962","unstructured":"J. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6:64\u201394, 1962.","journal-title":"Illinois Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/0-387-34805-0_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T05:28:22Z","timestamp":1619501302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/0-387-34805-0_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387973173"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/0-387-34805-0_45","relation":{},"subject":[]}}