{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T12:47:22Z","timestamp":1766407642564,"version":"3.40.5"},"reference-count":30,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The cryptographic task of position verification attempts to verify one party's location in spacetime by exploiting constraints on quantum information and relativistic causality. A popular verification scheme known as f<\/mml:mi><\/mml:math>-routing involves requiring the prover to redirect a quantum system based on the value of a Boolean function f<\/mml:mi><\/mml:math>. Cheating strategies for the f<\/mml:mi><\/mml:math>-routing scheme require the prover use pre-shared entanglement, and security of the scheme rests on assumptions about how much entanglement a prover can manipulate. Here, we give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme, and the authorization structure of the secret-sharing scheme is exploited to direct the system appropriately. This strategy completes the f<\/mml:mi><\/mml:math>-routing task using O<\/mml:mi>(<\/mml:mo>S<\/mml:mi>P<\/mml:mi>p<\/mml:mi><\/mml:msub>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>)<\/mml:mo><\/mml:math> EPR pairs, where S<\/mml:mi>P<\/mml:mi>p<\/mml:mi><\/mml:msub>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo><\/mml:math> is the minimal size of a span program over the field Z<\/mml:mi><\/mml:mrow>p<\/mml:mi><\/mml:msub><\/mml:math> computing f<\/mml:mi><\/mml:math>. This shows we can efficiently attack f<\/mml:mi><\/mml:math>-routing schemes whenever f<\/mml:mi><\/mml:math> is in the complexity class Mod<\/mml:mtext>p<\/mml:mi><\/mml:msub>L<\/mml:mtext><\/mml:math>, after allowing for local pre-processing. The best earlier construction achieved the class L, which is believed to be strictly inside of Mod<\/mml:mtext>p<\/mml:mi><\/mml:msub>L<\/mml:mtext><\/mml:math>. We also show that the size of a quantum secret sharing scheme with indicator function f<\/mml:mi>I<\/mml:mi><\/mml:msub><\/mml:math> upper bounds entanglement cost of f<\/mml:mi><\/mml:math>-routing on the function f<\/mml:mi>I<\/mml:mi><\/mml:msub><\/mml:math>.<\/jats:p>","DOI":"10.22331\/q-2023-08-09-1079","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T15:32:58Z","timestamp":1691595178000},"page":"1079","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":6,"title":["Code-routing: a new attack on position verification"],"prefix":"10.22331","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2283-3903","authenticated-orcid":false,"given":"Joy","family":"Cree","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4030-5410","authenticated-orcid":false,"given":"Alex","family":"May","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,8,9]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, pages 391\u2013407. Springer, 2009. https:\/\/doi.org\/10.1007\/978-3-642-03356-8_23.","DOI":"10.1007\/978-3-642-03356-8_23"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84 (1): 012326, 2011. https:\/\/doi.org\/10.1103\/PhysRevA.84.012326.","DOI":"10.1103\/PhysRevA.84.012326"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Adrian Kent. Quantum tasks in Minkowski space. Classical and Quantum Gravity, 29 (22): 224013, 2012. 10.1088\/0264-9381\/29\/22\/224013.","DOI":"10.1088\/0264-9381\/29\/22\/224013"},{"key":"3","doi-asserted-by":"publisher","unstructured":"William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299 (5886): 802\u2013803, 1982. https:\/\/doi.org\/10.1038\/299802a0.","DOI":"10.1038\/299802a0"},{"key":"4","unstructured":"Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, July 11 2006. US Patent 7,075,438."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Robert A Malaney. Location-dependent communications using quantum entanglement. Physical Review A, 81 (4): 042319, 2010. https:\/\/doi.org\/10.1103\/PhysRevA.81.042319.","DOI":"10.1103\/PhysRevA.81.042319"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43 (1): 150\u2013178, 2014. https:\/\/doi.org\/10.1137\/130913687.","DOI":"10.1137\/130913687"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Salman Beigi and Robert K\u00f6nig. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13 (9): 093036, 2011. 10.1088\/1367-2630\/13\/9\/093036.","DOI":"10.1088\/1367-2630\/13\/9\/093036"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1\u20134, 2022. https:\/\/doi.org\/10.1038\/s41567-022-01577-0.","DOI":"10.1038\/s41567-022-01577-0"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 145\u2013158, 2013. https:\/\/doi.org\/10.1145\/2422436.2422455.","DOI":"10.1145\/2422436.2422455"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Hartmut Klauck and Supartha Podder. New bounds for the garden-hose model. In Foundations of Software Technology and Theoretical Computer Science, 2014. 10.4230\/LIPIcs.FSTTCS.2014.481.","DOI":"10.4230\/LIPIcs.FSTTCS.2014.481"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam and Supartha Podder. Communication memento: Memoryless communication complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021. 10.4230\/LIPIcs.ITCS.2021.61.","DOI":"10.4230\/LIPIcs.ITCS.2021.61"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1\u201339, 2019. https:\/\/doi.org\/10.1007\/JHEP10(2019)233.","DOI":"10.1007\/JHEP10(2019)233"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020 (8): 1\u201334, 2020. https:\/\/doi.org\/10.1007\/JHEP08(2020)132.","DOI":"10.1007\/JHEP08(2020)132"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 6: 864, November 2022. ISSN 2521-327X. 10.22331\/q-2022-11-28-864. URL https:\/\/doi.org\/10.22331\/q-2022-11-28-864.","DOI":"10.22331\/q-2022-11-28-864"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Adam D Smith. Quantum secret sharing for general access structures. arXiv preprint quant-ph\/0001087, 2000. https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0001087.","DOI":"10.48550\/arXiv.quant-ph\/0001087"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Juan Maldacena. The large-N limit of superconformal field theories and supergravity. International journal of theoretical physics, 38 (4): 1113\u20131133, 1999. https:\/\/doi.org\/10.1023\/A:1026654312961.","DOI":"10.1023\/A:1026654312961"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Edward Witten. Anti-de sitter space and holography. Advances in Theoretical and Mathematical Physics, 2: 253\u2013291, 1998. 10.4310\/ATMP.1998.v2.n2.a2.","DOI":"10.4310\/ATMP.1998.v2.n2.a2"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. Theory of quantum secret sharing. Physical Review A, 61 (4): 042311, 2000. https:\/\/doi.org\/10.1103\/PhysRevA.61.042311.","DOI":"10.1103\/PhysRevA.61.042311"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Benjamin Schumacher and Michael A Nielsen. Quantum data processing and error correction. Physical Review A, 54 (4): 2629, 1996. https:\/\/doi.org\/10.1103\/PhysRevA.54.2629.","DOI":"10.1103\/PhysRevA.54.2629"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Benjamin Schumacher and Michael D Westmoreland. Approximate quantum error correction. Quantum Information Processing, 1 (1): 5\u201312, 2002. https:\/\/doi.org\/10.1023\/A:1019653202562.","DOI":"10.1023\/A:1019653202562"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, and Christoph Meinel. Structure and importance of logspace-mod class. Mathematical systems theory, 25 (3): 223\u2013237, 1992. https:\/\/doi.org\/10.1007\/BF01374526.","DOI":"10.1007\/BF01374526"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Mauricio Karchmer and Avi Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102\u2013111. IEEE, 1993. 10.1109\/SCT.1993.336536.","DOI":"10.1109\/SCT.1993.336536"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Neil D Jones, Y Edmund Lien, and William T Laaser. New problems complete for nondeterministic log space. Mathematical systems theory, 10 (1): 1\u201317, 1976. https:\/\/doi.org\/10.1007\/BF01683259.","DOI":"10.1007\/BF01683259"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal on Computing, 29 (4): 1118\u20131131, 2000. https:\/\/doi.org\/10.1137\/S0097539798339041.","DOI":"10.1137\/S0097539798339041"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, matching, and counting uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59 (2): 164\u2013181, 1999. https:\/\/doi.org\/10.1006\/jcss.1999.1646.","DOI":"10.1006\/jcss.1999.1646"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331\u2013360. Elsevier, 1997. https:\/\/doi.org\/10.1016\/S0065-2458(08)60342-3.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"27","unstructured":"Noam Nisan. The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty, 1: 301\u2013315, 1993."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A Cook. Exponential lower bounds for monotone span programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 406\u2013415. IEEE, 2016. 10.1109\/FOCS.2016.51.","DOI":"10.1109\/FOCS.2016.51"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1\u20139:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230\/LIPIcs.TQC.2016.9.","DOI":"10.4230\/LIPIcs.TQC.2016.9"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-09-1079\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T15:33:05Z","timestamp":1691595185000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-09-1079\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":30,"URL":"https:\/\/doi.org\/10.22331\/q-2023-08-09-1079","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2023,8,9]]},"article-number":"1079"}}