{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:05:54Z","timestamp":1757624754529,"version":"3.44.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032018779"},{"type":"electronic","value":"9783032018786"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01878-6_21","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T18:09:10Z","timestamp":1755367750000},"page":"642-673","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Compiled Nonlocal Games from\u00a0any Trapdoor Claw-Free Function"],"prefix":"10.1007","author":[{"given":"Kaniuar","family":"Bacho","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Kulpe","sequence":"additional","affiliation":[]},{"given":"Giulio","family":"Malavolta","sequence":"additional","affiliation":[]},{"given":"Simon","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Walter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Adcock, M., Cleve, R.: A quantum goldreich-levin theorem with cryptographic applications (2001). https:\/\/arxiv.org\/abs\/quant-ph\/0108095","DOI":"10.1007\/3-540-45841-7_26"},{"key":"21_CR2","doi-asserted-by":"publisher","unstructured":"Alamati, N., Malavolta, G., Rahimi, A.: Candidate trapdoor claw-free functions from group actions with applications to quantum protocols. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC\u00a02022, Part\u00a0I. LNCS, vol. 13747, pp. 266\u2013293. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-22318-1_10","DOI":"10.1007\/978-3-031-22318-1_10"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Arora, A.S., Bharti, K., Cojocaru, A., Coladangelo, A.: A computational test of quantum contextuality, and even simpler proofs of quantumness (2024). https:\/\/arxiv.org\/abs\/2405.06787","DOI":"10.1109\/FOCS61266.2024.00073"},{"key":"21_CR4","unstructured":"Bacho, K., Kulpe, A., Malavolta, G., Schmidt, S., Walter, M.: Compiled nonlocal games from any trapdoor claw-free function. Cryptology ePrint Archive, Paper 2024\/1829 (2024). https:\/\/eprint.iacr.org\/2024\/1829"},{"key":"21_CR5","unstructured":"Baroni, M., Vu, Q.H., Bourdoncle, B., Diamanti, E., Markham, D., \u0160upi\u0107, I.: Quantum bounds for compiled XOR games and $$d$$-outcome CHSH games. preprint arXiv:2403.05502 (2024)"},{"key":"21_CR6","doi-asserted-by":"publisher","unstructured":"Bartusek, J., et al.: Succinct classical verification of quantum computation. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO\u00a02022, Part\u00a0II. LNCS, vol. 13508, pp. 195\u2013211. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15979-4_7","DOI":"10.1007\/978-3-031-15979-4_7"},{"key":"21_CR7","unstructured":"Bartusek, J., Khurana, D.: On the power of oblivious state preparation. Cryptology ePrint Archive, Paper 2024\/1820 (2024). https:\/\/eprint.iacr.org\/2024\/1820"},{"issue":"3","key":"21_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","volume":"1","author":"JS Bell","year":"1964","unstructured":"Bell, J.S.: On the Einstein Podolsky Rosen paradox. Phys. Phys. Fizika 1(3), 195 (1964)","journal-title":"Phys. Phys. Fizika"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-96878-0_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"Z Brakerski","year":"2018","unstructured":"Brakerski, Z.: Quantum FHE (almost) as secure as\u00a0classical. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 67\u201395. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_3"},{"key":"21_CR10","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U.V., Vidick, T.: A cryptographic test of quantumness and certifiable randomness from a single quantum device. In: Thorup, M. (ed.) 59th FOCS, Paris, France, pp. 320\u2013331. IEEE Computer Society Press (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00038","DOI":"10.1109\/FOCS.2018.00038"},{"key":"21_CR11","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Gheorghiu, A., Kahanamoku-Meyer, G.D., Porat, E., Vidick, T.: Simple tests of quantumness also certify qubits. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO\u00a02023, Part\u00a0V. LNCS, vol. 14085, pp. 162\u2013191. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-38554-4_6","DOI":"10.1007\/978-3-031-38554-4_6"},{"key":"21_CR12","unstructured":"Brakerski, Z., Koppula, V., Vazirani, U., Vidick, T.: Simpler proofs of quantumness (2020). https:\/\/arxiv.org\/abs\/2005.04826"},{"key":"21_CR13","doi-asserted-by":"publisher","unstructured":"Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computation. In: 50th FOCS, Atlanta, GA, USA, pp. 517\u2013526. IEEE Computer Society Press (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.36","DOI":"10.1109\/FOCS.2009.36"},{"issue":"15","key":"21_CR14","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1103\/PhysRevLett.23.880","volume":"23","author":"JF Clauser","year":"1969","unstructured":"Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23(15), 880 (1969)","journal-title":"Phys. Rev. Lett."},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Cleve, R., Hoyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proceedings of 19th IEEE Annual Conference on Computational Complexity, pp. 236\u2013249 (2004). https:\/\/doi.org\/10.1109\/CCC.2004.1313847","DOI":"10.1109\/CCC.2004.1313847"},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-030-17659-4_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"A Coladangelo","year":"2019","unstructured":"Coladangelo, A., Grilo, A.B., Jeffery, S., Vidick, T.: Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 247\u2013277. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_9"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-030-84242-0_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"A Coladangelo","year":"2021","unstructured":"Coladangelo, A., Liu, J., Liu, Q., Zhandry, M.: Hidden cosets and applications to unclonable cryptography. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part I. LNCS, vol. 12825, pp. 556\u2013584. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84242-0_20"},{"key":"21_CR18","unstructured":"Cui, D., et al.: A computational Tsirelson\u2019s theorem for the value of compiled XOR games (2024). https:\/\/arxiv.org\/abs\/2402.17301"},{"key":"21_CR19","doi-asserted-by":"publisher","unstructured":"Danos, V., Kashefi, E.: Determinism in the one-way model. Phys. Rev. A 74, 052310 (2006). https:\/\/doi.org\/10.1103\/PhysRevA.74.052310","DOI":"10.1103\/PhysRevA.74.052310"},{"key":"21_CR20","doi-asserted-by":"publisher","unstructured":"Gheorghiu, A., Vidick, T.: Computationally-secure and composable remote state preparation. In: Zuckerman, D. (ed.) 60th FOCS, Baltimore, MD, USA, pp. 1024\u20131033. IEEE Computer Society Press (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00066","DOI":"10.1109\/FOCS.2019.00066"},{"key":"21_CR21","doi-asserted-by":"publisher","unstructured":"Grilo, A.B.: A simple protocol for verifiable delegation of quantum computation in one round. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0132, pp. 28:1\u201328:13. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.28. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ICALP.2019.28","DOI":"10.4230\/LIPIcs.ICALP.2019.28"},{"key":"21_CR22","doi-asserted-by":"publisher","unstructured":"Gupte, A., Vaikuntanathan, V.: How to construct quantum FHE, generically. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024, Part III, pp. 246\u2013279. Springer, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-68382-4_8","DOI":"10.1007\/978-3-031-68382-4_8"},{"issue":"11","key":"21_CR23","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1145\/3485628","volume":"64","author":"Z Ji","year":"2021","unstructured":"Ji, Z., Natarajan, A., Vidick, T., Wright, J., Yuen, H.: MIP* = RE. Commun. ACM 64(11), 131\u2013138 (2021)","journal-title":"Commun. ACM"},{"key":"21_CR24","doi-asserted-by":"publisher","unstructured":"Kahanamoku-Meyer, G.D., Choi, S., Vazirani, U.V., Yao, N.Y.: Classically verifiable quantum advantage from a computational bell test. Nat. Phys. 18(8), 918\u2013924 (2022). https:\/\/doi.org\/10.1038\/s41567-022-01643-7","DOI":"10.1038\/s41567-022-01643-7"},{"key":"21_CR25","doi-asserted-by":"publisher","unstructured":"Kalai, Y., Lombardi, A., Vaikuntanathan, V., Yang, L.: Quantum advantage from any non-local game. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 1617\u20131628. Association for Computing Machinery, New York (2023). https:\/\/doi.org\/10.1145\/3564246.3585164","DOI":"10.1145\/3564246.3585164"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Kulpe, A., Malavolta, G., Paddock, C., Schmidt, S., Walter, M.: A bound on the quantum value of all compiled nonlocal games (2024). https:\/\/arxiv.org\/abs\/2408.06711","DOI":"10.1145\/3717823.3718237"},{"key":"21_CR27","doi-asserted-by":"publisher","unstructured":"Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th FOCS, Paris, France, pp. 332\u2013338. IEEE Computer Society Press (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00039","DOI":"10.1109\/FOCS.2018.00039"},{"key":"21_CR28","doi-asserted-by":"publisher","unstructured":"Mahadev, U.: Classical verification of quantum computations. In: Thorup, M. (ed.) 59th FOCS, Paris, France, pp. 259\u2013267. IEEE Computer Society Press (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00033","DOI":"10.1109\/FOCS.2018.00033"},{"issue":"1","key":"21_CR29","doi-asserted-by":"publisher","first-page":"42861","DOI":"10.1038\/srep42861","volume":"7","author":"A Mantri","year":"2017","unstructured":"Mantri, A., Demarie, T.F., Fitzsimons, J.F.: Universality of quantum computation with cluster states and (x, y)-plane measurements. Sci. Rep. 7(1), 42861 (2017). https:\/\/doi.org\/10.1038\/srep42861","journal-title":"Sci. Rep."},{"key":"21_CR30","unstructured":"Mehta, A., Paddock, C., Wooltorton, L.: Self-testing in the compiled setting via tilted-CHSH inequalities. preprint arXiv:2406.04986 (2024)"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Metger, T., Natarajan, A., Zhang, T.: Succinct arguments for QMA from standard assumptions via compiled nonlocal games (2024). https:\/\/arxiv.org\/abs\/2404.19754","DOI":"10.1109\/FOCS61266.2024.00078"},{"key":"21_CR32","doi-asserted-by":"publisher","unstructured":"Natarajan, A., Zhang, T.: Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1342\u20131348 (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00081","DOI":"10.1109\/FOCS57990.2023.00081"},{"key":"21_CR33","doi-asserted-by":"publisher","first-page":"5188","DOI":"10.1103\/PhysRevLett.86.5188","volume":"86","author":"R Raussendorf","year":"2001","unstructured":"Raussendorf, R., Briegel, H.J.: A one-way quantum computer. Phys. Rev. Lett. 86, 5188\u20135191 (2001). https:\/\/doi.org\/10.1103\/PhysRevLett.86.5188","journal-title":"Phys. Rev. Lett."},{"issue":"7446","key":"21_CR34","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1038\/nature12035","volume":"496","author":"BW Reichardt","year":"2013","unstructured":"Reichardt, B.W., Unger, F., Vazirani, U.: Classical command of quantum systems. Nature 496(7446), 456\u2013460 (2013)","journal-title":"Nature"},{"key":"21_CR35","doi-asserted-by":"crossref","unstructured":"Slofstra, W.: The set of quantum correlations is not closed. Forum Math. Pi 7 (2017). https:\/\/api.semanticscholar.org\/CorpusID:119733698","DOI":"10.1017\/fmp.2018.3"},{"key":"21_CR36","unstructured":"Vidick, T.: Course FSMP, fall\u201920: interactions with quantum devices (2020). http:\/\/users.cms.caltech.edu\/~vidick\/teaching\/fsmp\/fsmp.pdf"},{"key":"21_CR37","unstructured":"Zhang, J.: Formulations and constructions of remote state preparation with verifiability, with applications. Cryptology ePrint Archive, Paper 2023\/1490 (2023). https:\/\/eprint.iacr.org\/2023\/1490"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01878-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T15:12:04Z","timestamp":1757430724000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01878-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018779","9783032018786"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01878-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}