{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:26Z","timestamp":1781077946770,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","funder":[{"name":"JST CREST","award":["JPMJCR23I3"],"award-info":[{"award-number":["JPMJCR23I3"]}]},{"name":"JST Moonshot R&D","award":["JPMJMS2061-5-1-1"],"award-info":[{"award-number":["JPMJMS2061-5-1-1"]}]},{"name":"JST FOREST","award":[""],"award-info":[{"award-number":[""]}]},{"name":"MEXT QLEAP","award":[""],"award-info":[{"award-number":[""]}]},{"name":"JSPS","award":["21H05183, 22H00522"],"award-info":[{"award-number":["21H05183, 22H00522"]}]},{"name":"JST SPRING","award":["JPMJSP2110"],"award-info":[{"award-number":["JPMJSP2110"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718133","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1863-1874","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Cryptographic Characterization of Quantum Advantage"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7424-4372","authenticated-orcid":false,"given":"Tomoyuki","family":"Morimae","sequence":"first","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9119-876X","authenticated-orcid":false,"given":"Yuki","family":"Shirakawa","sequence":"additional","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1712-3026","authenticated-orcid":false,"given":"Takashi","family":"Yamakawa","sequence":"additional","affiliation":[{"name":"NTT, Tokyo, Japan"},{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9527-3"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993682"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.1"},{"key":"e_1_3_2_1_5_1","unstructured":"Scott Aaronson and Lijie Chen. 2017. Complexity-theoretic foundations of quantum supremacy experiments."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a011"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_8"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2025.8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585153"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_2"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84242-0_17"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15979-4_7"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0318-2"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.24"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3441309"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aar3106"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2010.0301"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"e_1_3_2_1_20_1","unstructured":"Bruno P. Cavalar Eli Goldin Matthew Gray and Peter Hall. 2024. A Meta-Complexity Characterization of Quantum Cryptography. arxiv:2410.04984. arxiv:2410.04984"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68394-7_8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1651"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.200502"},{"key":"e_1_3_2_1_24_1","unstructured":"Eli Goldin Tomoyuki Morimae Saachi Mutreja and Takashi Yamakawa. 2024. CountCrypt: Quantum Cryptography between QCMA and PP. Cryptology ePrint Archive Paper 2024\/1707. https:\/\/eprint.iacr.org\/2024\/1707"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6_18"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/080725404"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_6"},{"key":"e_1_3_2_1_28_1","unstructured":"Taiga Hiroka and Tomoyuki Morimae. 2024. Quantum Cryptography from Meta-Complexity. Cryptology ePrint Archive Paper 2024\/1539. https:\/\/eprint.iacr.org\/2024\/1539"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96878-0_5"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-022-01643-7"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585164"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649654"},{"key":"e_1_3_2_1_34_1","unstructured":"Dakshita Khurana and Kabir Tomer. 2024. Founding Quantum Cryptography on Quantum Advantage or Towards Cryptography from # P-Hardness. Cryptology ePrint Archive Paper 2024\/1490. https:\/\/eprint.iacr.org\/2024\/1490"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.TQC.2021.2"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585225"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22185"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649650"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.040302"},{"key":"e_1_3_2_1_40_1","unstructured":"Tomoyuki Morimae Yuki Shirakawa and Takashi Yamakawa. 2024. Cryptographic Characterization of Quantum Advantage. arxiv:2410.00499. arxiv:2410.00499"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae Shogo Yamada and Takashi Yamakawa. 2024. Quantum Unpredictability. LNCS. Springer Singapore 3\u201332. https:\/\/doi.org\/10.1007\/978-981-96-0947-5_1 10.1007\/978-981-96-0947-5_1","DOI":"10.1007\/978-981-96-0947-5_1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_10"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.87"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68388-6_13"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160253"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_1_48_1","first-page":"134","article-title":"Adaptive quantum computation, constant-depth circuits and Arthur-Merlin games","volume":"4","author":"Terhal B. M.","year":"2004","unstructured":"B. M. Terhal and D. P. DiVincenzo. 2004. Adaptive quantum computation, constant-depth circuits and Arthur-Merlin games.. Quant. Inf. Comput., 4, 2 (2004), 134\u2013145.","journal-title":"Quant. Inf. Comput."},{"key":"e_1_3_2_1_49_1","series-title":"SIAM J. Comput","volume-title":"An Unconditional Study of Computational Zero Knowledge","author":"Vadhan Salil P.","unstructured":"Salil P. Vadhan. 2006. An Unconditional Study of Computational Zero Knowledge. SIAM J. Comput.."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658665"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:47Z","timestamp":1750693187000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":50,"alternative-id":["10.1145\/3717823.3718133","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718133","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}