Code-routing: a new attack on position verification

Joy Cree; Alex May

doi:10.22331/q-2023-08-09-1079

Code-routing: a new attack on position verification

Stanford University

Published:	2023-08-09, volume 7, page 1079
Eprint:	arXiv:2202.07812v5
Doi:	https://doi.org/10.22331/q-2023-08-09-1079
Citation:	Quantum 7, 1079 (2023).

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

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$-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

@article{Cree2023coderoutingnew,
  doi = {10.22331/q-2023-08-09-1079},
  url = {https://doi.org/10.22331/q-2023-08-09-1079},
  title = {Code-routing: a new attack on position verification},
  author = {Cree, Joy and May, Alex},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1079},
  month = aug,
  year = {2023}
}

► 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://doi.org/10.1007/978-3-642-03356-8_23.
https://doi.org/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://doi.org/10.1103/PhysRevA.84.012326.
https://doi.org/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.
https://doi.org/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://doi.org/10.1038/299802a0.
https://doi.org/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://doi.org/10.1103/PhysRevA.81.042319.
https://doi.org/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://doi.org/10.1137/130913687.
https://doi.org/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.
https://doi.org/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://doi.org/10.1038/s41567-022-01577-0.
https://doi.org/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://doi.org/10.1145/2422436.2422455.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.4230/LIPIcs.ITCS.2021.61

[13] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https://doi.org/10.1007/JHEP10(2019)233.
https://doi.org/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://doi.org/10.1007/JHEP08(2020)132.
https://doi.org/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://doi.org/10.22331/q-2022-11-28-864.
https://doi.org/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://doi.org/10.48550/arXiv.quant-ph/0001087.
https://doi.org/10.48550/arXiv.quant-ph/0001087
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://doi.org/10.1023/A:1026654312961.
https://doi.org/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.
https://doi.org/10.4310/ATMP.1998.v2.n2.a2

[19] Daniel Gottesman. Theory of quantum secret sharing. Physical Review A, 61 (4): 042311, 2000. https://doi.org/10.1103/PhysRevA.61.042311.
https://doi.org/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://doi.org/10.1103/PhysRevA.54.2629.
https://doi.org/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://doi.org/10.1023/A:1019653202562.
https://doi.org/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://doi.org/10.1007/BF01374526.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/BF01683259.
https://doi.org/10.1007/BF01683259

[25] Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https://doi.org/10.1137/S0097539798339041.
https://doi.org/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://doi.org/10.1006/jcss.1999.1646.
https://doi.org/10.1006/jcss.1999.1646

[27] Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997. https://doi.org/10.1016/S0065-2458(08)60342-3.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.4230/LIPIcs.TQC.2016.9

Cited by

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

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

[3] 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).

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

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

[6] 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).

[7] Llorenç Escolà-Farràs and Florian Speelman, "Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers", arXiv:2212.03674, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-09-22 11:33:57). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-09-22 11:33:56).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.