{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:52:54Z","timestamp":1771703574428,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642365935","type":"print"},{"value":"9783642365942","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_16","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"281-296","source":"Crossref","is-referenced-by-count":11,"title":["Feasibility and Completeness of Cryptographic Tasks in the Quantum World"],"prefix":"10.1007","author":[{"given":"Serge","family":"Fehr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong-Sheng","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vassilis","family":"Zikas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 186\u2013195. IEEE (October 2004)","DOI":"10.1109\/FOCS.2004.71"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Cr\u00e9peau, C., Gottesman, D., Hassidim, A., Smith, A.: Secure multiparty quantum computation with (only) a strict honest majority. In: 47th Annual Symposium on Foundations of Computer Science (FOCS), pp. 249\u2013260. IEEE (October 2006)","DOI":"10.1109\/FOCS.2006.68"},{"key":"16_CR3","unstructured":"Bennett, C., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers Systems and Signal Processing, Bangalore, India, pp. 175\u2013179 (December 1984)"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/3-540-46766-1_29","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"C.H. Bennett","year":"1992","unstructured":"Bennett, C.H., Brassard, G., Cr\u00e9peau, C., Skubiszewska, M.-H.: Practical Quantum Oblivious Transfer. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 351\u2013366. Springer, Heidelberg (1992)"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/978-3-642-14623-7_39","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"N.J. Bouman","year":"2010","unstructured":"Bouman, N.J., Fehr, S.: Sampling in a Quantum Population, and Applications. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 724\u2013741. Springer, Heidelberg (2010)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.109.160501","volume":"109","author":"H. Buhrman","year":"2012","unstructured":"Buhrman, H., Christandl, M., Schaffner, C.: Complete insecurity of quantum protocols for classical two-party computation. Phys. Rev. Lett.\u00a0109, 160501 (2012)","journal-title":"Phys. Rev. Lett."},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R. Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology\u00a013(1), 143\u2013202 (2000)","journal-title":"Journal of Cryptology"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136\u2013145. IEEE (October 2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-44647-8_2","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"R. Canetti","year":"2001","unstructured":"Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.\u00a02139, pp. 19\u201340. Springer, Heidelberg (2001)"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00145-005-0419-9","volume":"19","author":"R. Canetti","year":"2006","unstructured":"Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. Journal of Cryptology\u00a019(2), 135\u2013167 (2006)","journal-title":"Journal of Cryptology"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 494\u2013503. ACM Press (May 2002)","DOI":"10.1145\/509978.509980"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Canetti, R., Pass, R., Shelat, A.: Cryptography from sunspots: How to use an imperfect reference string. In: 48th Annual Symposium on Foundations of Computer Science (FOCS), pp. 249\u2013259. IEEE (October 2007)","DOI":"10.1109\/FOCS.2007.70"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Cr\u00e9peau, C., Gottesman, D., Smith, A.: Secure multi-party quantum computation. In: 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 643\u2013652. ACM Press (May 2002)","DOI":"10.1145\/509907.510000"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-25385-0_22","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"C. Cr\u00e9peau","year":"2011","unstructured":"Cr\u00e9peau, C., Salvail, L., Simard, J.-R., Tapp, A.: Two Provers in Isolation. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 407\u2013430. Springer, Heidelberg (2011)"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-642-03356-8_24","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"I. Damg\u00e5rd","year":"2009","unstructured":"Damg\u00e5rd, I., Fehr, S., Lunemann, C., Salvail, L., Schaffner, C.: Improving the Security of Quantum Protocols via Commit-and-Open. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 408\u2013427. Springer, Heidelberg (2009)"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1007\/978-3-642-32009-5_46","volume-title":"Crypto 2012","author":"F. Dupuis","year":"2012","unstructured":"Dupuis, F., Nielsen, J.B., Salvail, L.: Actively Secure Two-Party Evaluation of Any Quantum Operation. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol.\u00a07417, pp. 794\u2013811. Springer, Heidelberg (2012)"},{"key":"16_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-22792-9_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S. Hallgren","year":"2011","unstructured":"Hallgren, S., Smith, A., Song, F.: Classical Cryptographic Protocols in a Quantum World. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 411\u2013428. Springer, Heidelberg (2011)"},{"key":"16_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-85174-5_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"Y. Ishai","year":"2008","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer \u2013 Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-540-72540-4_7","volume-title":"Advances in Cryptology - EUROCRYPT 2007","author":"J. Katz","year":"2007","unstructured":"Katz, J.: Universally Composable Multi-party Computation Using Tamper-Proof Hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol.\u00a04515, pp. 115\u2013128. Springer, Heidelberg (2007)"},{"key":"16_CR20","unstructured":"Katz, J., Kiayias, A., Kumaresan, R., Shelat, A., Zhou, H.-S.: From impossibility to completeness for deterministic two-party SFE (2011) (manuscript)"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20\u201331. ACM (1988)","DOI":"10.1145\/62212.62215"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-19571-6_22","volume-title":"Theory of Cryptography","author":"D. Kraschewski","year":"2011","unstructured":"Kraschewski, D., M\u00fcller-Quade, J.: Completeness Theorems with Constructive Proofs for Finite Deterministic 2-Party Functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 364\u2013381. Springer, Heidelberg (2011)"},{"issue":"2","key":"16_CR23","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1103\/PhysRevA.56.1154","volume":"56","author":"H.-K. Lo","year":"1997","unstructured":"Lo, H.-K.: Insecurity of quantum secure computations. Physical Review A\u00a056(2), 1154\u20131162 (1997)","journal-title":"Physical Review A"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"3410","DOI":"10.1103\/PhysRevLett.78.3410","volume":"78","author":"H.K. Lo","year":"1997","unstructured":"Lo, H.K., Chau, H.F.: Is quantum bit commitment really possible? Physical Review Letters\u00a078, 3410\u20133413 (1997)","journal-title":"Physical Review Letters"},{"issue":"5410","key":"16_CR25","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.1126\/science.283.5410.2050","volume":"283","author":"H.-K. Lo","year":"1999","unstructured":"Lo, H.-K., Chau, H.F.: Unconditional security of quantum key distribution over arbitrarily long distances. Science\u00a0283(5410), 2050\u20132056 (1999)","journal-title":"Science"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-21969-6_2","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2011","author":"C. Lunemann","year":"2011","unstructured":"Lunemann, C., Nielsen, J.B.: Fully Simulatable Quantum-Secure Coin-Flipping and Applications. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol.\u00a06737, pp. 21\u201340. Springer, Heidelberg (2011)"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-00457-5_16","volume-title":"Theory of Cryptography","author":"H.K. Maji","year":"2009","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Complexity of Multi-party Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 256\u2013273. Springer, Heidelberg (2009)"},{"key":"16_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-14623-7_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"H.K. Maji","year":"2010","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 595\u2013612. Springer, Heidelberg (2010)"},{"key":"16_CR29","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1103\/PhysRevLett.78.3414","volume":"78","author":"D. Mayers","year":"1997","unstructured":"Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Physical Review Letters\u00a078, 3414\u20133417 (1997)","journal-title":"Physical Review Letters"},{"issue":"3","key":"16_CR30","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/382780.382781","volume":"48","author":"D. Mayers","year":"2001","unstructured":"Mayers, D.: Unconditional security in quantum cryptography. J. ACM\u00a048(3), 351\u2013406 (2001)","journal-title":"J. ACM"},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"85006","DOI":"10.1088\/1367-2630\/11\/8\/085006","volume":"11","author":"J. M\u00fcller-Quade","year":"2009","unstructured":"M\u00fcller-Quade, J., Renner, R.: Composability in quantum cryptography. New J. Phys.\u00a011, 085006 (2009)","journal-title":"New J. Phys."},{"key":"16_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-540-85174-5_15","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"M. Prabhakaran","year":"2008","unstructured":"Prabhakaran, M., Rosulek, M.: Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 262\u2013279. Springer, Heidelberg (2008)"},{"key":"16_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-32009-5_24","volume-title":"Crypto 2012","author":"M. Rosulek","year":"2012","unstructured":"Rosulek, M.: Universal Composability from Essentially Any Trusted Setup. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol.\u00a07417, pp. 406\u2013423. Springer, Heidelberg (2012)"},{"key":"16_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-10366-7_5","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"L. Salvail","year":"2009","unstructured":"Salvail, L., Schaffner, C., Sot\u00e1kov\u00e1, M.: On the Power of Two-Party Quantum Cryptography. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 70\u201387. Springer, Heidelberg (2009)"},{"issue":"2","key":"16_CR35","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1103\/PhysRevLett.85.441","volume":"85","author":"P.W. Shor","year":"2000","unstructured":"Shor, P.W., Preskill, J.: Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett.\u00a085(2), 441\u2013444 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"16_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-642-13190-5_25","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"D. Unruh","year":"2010","unstructured":"Unruh, D.: Universally Composable Quantum Multi-party Computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 486\u2013505. Springer, Heidelberg (2010)"},{"issue":"1","key":"16_CR37","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1137\/060670997","volume":"39","author":"J. Watrous","year":"2009","unstructured":"Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput.\u00a039(1), 25\u201358 (2009); Preliminary version in STOC 2006","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:20Z","timestamp":1745957480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}