{"corpus_id":215541966,"paper_sha":"f2b3c18ef4743855d29fce2f07c6aaabc2d0133d","doi":"10.1103/PhysRevLett.109.160501","arxiv_id":"1201.0849","pmid":23215060,"pmcid":null,"mag_id":2012772813,"dblp_id":"journals/corr/abs-1201-0849","acl_id":null,"title":"Complete Insecurity of Quantum Protocols for Classical Two-Party Computation","year":2012,"publication_date":"2012-01-04","venue":"Physical Review Letters","journal":{"name":"Physical review letters","pages":"\n          160501\n        ","volume":"109 16"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":["Journal Article"],"s2_fields_of_study":["Medicine","Physics","Computer Science"],"reference_count":32,"citation_count":80,"influential_citation_count":3,"is_open_access":true,"arxiv_categories":["quant-ph","cs.CR"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":"Phys. Rev. Lett. 109, 160501 (2012)","mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":5,"s2_open_access_pdf_url":"http://link.aps.org/pdf/10.1103/PhysRevLett.109.160501","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/f2b3c18ef4743855d29fce2f07c6aaabc2d0133d","s2_open_access_license":"CCBY","s2_open_access_status":"HYBRID","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"A fundamental task in modern cryptography is the joint computation of a function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more about the other's input than what is implied by the value of the function. In this Letter, we show that any quantum protocol for the computation of a classical deterministic function that outputs the result to both parties (two-sided computation) and that is secure against a cheating Bob can be completely broken by a cheating Alice. Whereas it is known that quantum protocols for this task cannot be completely secure, our result implies that security for one party implies complete insecurity for the other. Our findings stand in stark contrast to recent protocols for weak coin tossing and highlight the limits of cryptography within quantum mechanics. We remark that our conclusions remain valid, even if security is only required to be approximate and if the function that is computed for Bob is different from that of Alice.","claims":[{"public_id":"cl_fbb6a70387cfefae17e28f66273641c6","status":"active","text":"Any quantum protocol for computing a classical deterministic function with outputs delivered to both parties and secure against a cheating Bob can be completely broken by a cheating Alice.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_fbb6a70387cfefae17e28f66273641c6"},{"public_id":"cl_f1f2ad97f0b313fc046de438a640e088","status":"active","text":"Security for one party implies complete insecurity for the other in this class of two-party quantum computation protocols.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_f1f2ad97f0b313fc046de438a640e088"},{"public_id":"cl_42d967690d40d082697b97eb539dbbc3","status":"active","text":"The impossibility result remains valid under approximate security requirements and even when Alice's and Bob's computed functions differ.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_42d967690d40d082697b97eb539dbbc3"}],"concepts":[{"public_id":"co_10bc9dd07e2976f529cdd27558cc7ab5","status":"active","name":"two-sided computation","description":"A computation setting in which the result of the function is delivered to both parties.","types":["computation model"],"aliases":["output to both parties"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_10bc9dd07e2976f529cdd27558cc7ab5"},{"public_id":"co_148bac01af4a07cefab2613d570593c6","status":"active","name":"approximate security","description":"A relaxed security notion allowing small deviations from ideal security guarantees.","types":["security property"],"aliases":["imperfect security"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_148bac01af4a07cefab2613d570593c6"},{"public_id":"co_1f35f1bf975e875da706cdc720587de1","status":"active","name":"complete insecurity","description":"A failure mode in which one party can fully break the protocol's privacy or correctness guarantees.","types":["security failure"],"aliases":["complete break"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1f35f1bf975e875da706cdc720587de1"},{"public_id":"co_685163691f09dd7d4ca629fa752d319f","status":"active","name":"cheating Bob","description":"An adversarial Bob who deviates from the protocol in order to gain information or influence the output.","types":["adversary"],"aliases":["dishonest Bob"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_685163691f09dd7d4ca629fa752d319f"},{"public_id":"co_81ea04679f7e0d5efc50bed5cf5b1046","status":"active","name":"different output functions for Alice and Bob","description":"A variant of the computation setting where the two parties may receive different functions of the inputs.","types":["protocol variant"],"aliases":["asymmetric outputs"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_81ea04679f7e0d5efc50bed5cf5b1046"},{"public_id":"co_9444b525db613b78a61d4bf7cfd92890","status":"active","name":"two-party computation","description":"A cryptographic task where two parties jointly compute a function of their private inputs.","types":["cryptographic task"],"aliases":["secure two-party computation"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_9444b525db613b78a61d4bf7cfd92890"},{"public_id":"co_9970b404a6e8745b46f616fbb5000e91","status":"active","name":"cheating Alice","description":"An adversarial Alice who deviates from the protocol in order to gain information or influence the output.","types":["adversary"],"aliases":["dishonest Alice"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_9970b404a6e8745b46f616fbb5000e91"},{"public_id":"co_c49a5d0e0c826d97bf8191d27327ca51","status":"active","name":"security for one party","description":"A security guarantee against cheating by one designated party in the protocol.","types":["security property"],"aliases":["one-sided security"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c49a5d0e0c826d97bf8191d27327ca51"},{"public_id":"co_d026448f522ac7bcf6cd7428cde6b942","status":"active","name":"quantum protocol for classical deterministic function","description":"A quantum cryptographic protocol intended to compute a deterministic classical function from inputs held by two parties.","types":["protocol","cryptographic protocol"],"aliases":["quantum protocol for classical two-party computation"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d026448f522ac7bcf6cd7428cde6b942"}],"external_ids":{"DOI":"10.1103/PhysRevLett.109.160501","ArXiv":"1201.0849","PubMed":23215060,"PubMedCentral":null,"MAG":2012772813,"DBLP":"journals/corr/abs-1201-0849","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"http://link.aps.org/pdf/10.1103/PhysRevLett.109.160501","landing_url":"https://www.semanticscholar.org/paper/f2b3c18ef4743855d29fce2f07c6aaabc2d0133d","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":"CCBY","status":"HYBRID","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":5},"paper_id":632319,"paper_uid":"43d24a8f-9e3a-4561-9f15-35b5f1a03145","canonical_identity":{"paper_id":632319,"paper_uid":"43d24a8f-9e3a-4561-9f15-35b5f1a03145","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/215541966"}