Code-routing: a new attack on position verification

Joy Cree and Alex May

Stanford University

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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$-routing involves requiring the prover to redirect a quantum system based on the value of a Boolean function $f$. Cheating strategies for the $f$-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$-routing task using $O(SP_p(f))$ EPR pairs, where $SP_p(f)$ is the minimal size of a span program over the field $\mathbb{Z}_p$ computing $f$. This shows we can efficiently attack $f$-routing schemes whenever $f$ is in the complexity class $\text{Mod}_p\text{L}$, after allowing for local pre-processing. The best earlier construction achieved the class L, which is believed to be strictly inside of $\text{Mod}_p\text{L}$. We also show that the size of a quantum secret sharing scheme with indicator function $f_I$ upper bounds entanglement cost of $f$-routing on the function $f_I$.

► BibTeX data

► References

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, pages 391–407. Springer, 2009. https:/​/​​10.1007/​978-3-642-03356-8_23.

[2] 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:/​/​​10.1103/​PhysRevA.84.012326.

[3] Adrian Kent. Quantum tasks in Minkowski space. Classical and Quantum Gravity, 29 (22): 224013, 2012. 10.1088/​0264-9381/​29/​22/​224013.

[4] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299 (5886): 802–803, 1982. https:/​/​​10.1038/​299802a0.

[5] Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, July 11 2006. US Patent 7,075,438.

[6] Robert A Malaney. Location-dependent communications using quantum entanglement. Physical Review A, 81 (4): 042319, 2010. https:/​/​​10.1103/​PhysRevA.81.042319.

[7] 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–178, 2014. https:/​/​​10.1137/​130913687.

[8] Salman Beigi and Robert König. 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.

[9] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1–4, 2022. https:/​/​​10.1038/​s41567-022-01577-0.

[10] 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–158, 2013. https:/​/​​10.1145/​2422436.2422455.

[11] 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.

[12] 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ür Informatik, 2021. 10.4230/​LIPIcs.ITCS.2021.61.

[13] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https:/​/​​10.1007/​JHEP10(2019)233.

[14] Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020 (8): 1–34, 2020. https:/​/​​10.1007/​JHEP08(2020)132.

[15] 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:/​/​​10.22331/​q-2022-11-28-864.

[16] Adam D Smith. Quantum secret sharing for general access structures. arXiv preprint quant-ph/​0001087, 2000. https:/​/​​10.48550/​arXiv.quant-ph/​0001087.

[17] Juan Maldacena. The large-N limit of superconformal field theories and supergravity. International journal of theoretical physics, 38 (4): 1113–1133, 1999. https:/​/​​10.1023/​A:1026654312961.

[18] Edward Witten. Anti-de sitter space and holography. Advances in Theoretical and Mathematical Physics, 2: 253–291, 1998. 10.4310/​ATMP.1998.v2.n2.a2.

[19] Daniel Gottesman. Theory of quantum secret sharing. Physical Review A, 61 (4): 042311, 2000. https:/​/​​10.1103/​PhysRevA.61.042311.

[20] Benjamin Schumacher and Michael A Nielsen. Quantum data processing and error correction. Physical Review A, 54 (4): 2629, 1996. https:/​/​​10.1103/​PhysRevA.54.2629.

[21] Benjamin Schumacher and Michael D Westmoreland. Approximate quantum error correction. Quantum Information Processing, 1 (1): 5–12, 2002. https:/​/​​10.1023/​A:1019653202562.

[22] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, and Christoph Meinel. Structure and importance of logspace-mod class. Mathematical systems theory, 25 (3): 223–237, 1992. https:/​/​​10.1007/​BF01374526.

[23] Mauricio Karchmer and Avi Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.

[24] Neil D Jones, Y Edmund Lien, and William T Laaser. New problems complete for nondeterministic log space. Mathematical systems theory, 10 (1): 1–17, 1976. https:/​/​​10.1007/​BF01683259.

[25] Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https:/​/​​10.1137/​S0097539798339041.

[26] 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–181, 1999. https:/​/​​10.1006/​jcss.1999.1646.

[27] Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997. https:/​/​​10.1016/​S0065-2458(08)60342-3.

[28] Noam Nisan. The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty, 1: 301–315, 1993.

[29] 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–415. IEEE, 2016. 10.1109/​FOCS.2016.51.

[30] 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–9:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230/​LIPIcs.TQC.2016.9.

Cited by

[1] Llorenç Escolà-Farràs and Florian Speelman, "Single-Qubit Loss-Tolerant Quantum Position Verification Protocol Secure against Entangled Attackers", Physical Review Letters 131 14, 140802 (2023).

[2] Alex May, "Complexity and entanglement in non-local computation and holography", Quantum 6, 864 (2022).

[3] Alex May, Jonathan Sorce, and Beni Yoshida, "The connected wedge theorem and its consequences", Journal of High Energy Physics 2022 11, 153 (2022).

[4] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel, "Relating non-local quantum computation to information theoretic cryptography", arXiv:2306.16462, (2023).

[5] Kfir Dolev and Sam Cree, "Non-local computation of quantum circuits with small light cones", arXiv:2203.10106, (2022).

[6] Rene Allerstorfer, Llorenç Escolà-Farràs, Arpan Akash Ray, Boris Škorić, Florian Speelman, and Philip Verduyn Lunel, "Security of a Continuous-Variable based Quantum Position Verification Protocol", arXiv:2308.04166, (2023).

[7] Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell, "Conditional disclosure of secrets with quantum resources", arXiv:2404.14491, (2024).

[8] Kfir Dolev and Sam Cree, "Holography as a resource for non-local quantum computation", arXiv:2210.13500, (2022).

[9] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May, "Linear gate bounds against natural functions for position-verification", arXiv:2402.18648, (2024).

[10] Llorenç Escolà-Farràs and Florian Speelman, "Lossy-and-Constrained Extended Non-Local Games with Applications to Cryptography: BC, QKD and QPV", arXiv:2405.13717, (2024).

[11] Rene Allerstorfer, Llorenç Escolà-Farràs, Arpan Akash Ray, Boris Skoric, and Florian Speelman, "Continuous-variable Quantum Position Verification secure against entangled attackers", arXiv:2404.14261, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 02:55:18) and SAO/NASA ADS (last updated successfully 2024-06-22 02:55:19). The list may be incomplete as not all publishers provide suitable and complete citation data.