Code-Routing: ein neuer Angriff auf die Positionsüberprüfung

Code-Routing: ein neuer Angriff auf die Positionsüberprüfung

Zeitstempel: 9. August 2023, 11:18 Uhr
Code-Routing: ein neuer Angriff auf die Positionsüberprüfung PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Joy Cree und Alex Mai

Stanford University

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Die kryptografische Aufgabe der Positionsüberprüfung versucht, den Standort einer Partei in der Raumzeit zu überprüfen, indem sie Einschränkungen der Quanteninformation und relativistische Kausalität ausnutzt. Ein beliebtes Verifizierungsschema, das als $f$-Routing bekannt ist, besteht darin, dass der Prüfer ein Quantensystem basierend auf dem Wert einer booleschen Funktion $f$ umleiten muss. Betrugsstrategien für das $f$-Routing-Schema erfordern, dass der Prüfer eine vorab geteilte Verschränkung verwendet, und die Sicherheit des Schemas beruht auf Annahmen darüber, wie viel Verschränkung ein Prüfer manipulieren kann. Hier stellen wir eine neue Betrugsstrategie vor, bei der das Quantensystem in ein Schema zur gemeinsamen Nutzung von Geheimnissen kodiert wird und die Autorisierungsstruktur des Schemas zur gemeinsamen Nutzung von Geheimnissen ausgenutzt wird, um das System entsprechend zu steuern. Diese Strategie schließt die $f$-Routing-Aufgabe unter Verwendung von $O(SP_p(f))$ EPR-Paaren ab, wobei $SP_p(f)$ die minimale Größe eines Span-Programms über das Feld $mathbb{Z}_p$ zur Berechnung von $ ist f$. Dies zeigt, dass wir $f$-Routing-Schemata effizient angreifen können, wann immer sich $f$ in der Komplexitätsklasse $text{Mod}_ptext{L}$ befindet, nachdem wir die lokale Vorverarbeitung berücksichtigt haben. Die beste frühere Konstruktion erreichte die Klasse L, von der angenommen wird, dass sie ausschließlich innerhalb von $text{Mod}_ptext{L}$ liegt. Wir zeigen auch, dass die Größe eines Schemas zur gemeinsamen Nutzung von Quantengeheimnissen mit der Indikatorfunktion $f_I$ die oberen Grenzen der Verschränkungskosten des $f$-Routings auf der Funktion $f_I$ begrenzt.

► BibTeX-Daten

► Referenzen

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty und Rafail Ostrovsky. Positionsbasierte Kryptographie. In Annual International Cryptology Conference, Seiten 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 und Timothy P. Spiller. Quantum Tagging: Authentifizieren des Standorts über Quanteninformationen und relativistische Signalisierungsbeschränkungen. 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. Quantenaufgaben im Minkowski-Raum. 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 und Wojciech H. Zurek. Ein einzelnes Quant kann nicht geklont werden. 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 und Raymond G. Beausoleil. Tagging Systems, 11. Juli 2006. US-Patent 7,075,438.

[6] Robert A Malaney. Ortsabhängige Kommunikation mittels Quantenverschränkung. 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 und Christian Schaffner. Positionsbasierte Quantenkryptographie: Unmöglichkeit und Konstruktionen. SIAM Journal on Computing, 43 (1): 150–178, 2014. https:/​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi und Robert König. Vereinfachte sofortige nicht-lokale Quantenberechnung mit Anwendungen in der positionsbasierten Kryptografie. 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 und Florian Speelman. Ein Einzel-Qubit-Positionsüberprüfungsprotokoll, das vor Multi-Qubit-Angriffen sicher ist. Nature Physics, Seiten 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 und Florian Speelman. Das Gartenschlauch-Modell. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, Seiten 145–158, 2013. https:/​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck und Supartha Podder. Neue Grenzen für das Gartenschlauchmodell. 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 und Supartha Podder. Erinnerung an die Kommunikation: Erinnerungslose Kommunikationskomplexität. Auf der 12. 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. Quantenaufgaben in der Holographie. 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 und Jonathan Sorce. Holografische Streuung erfordert einen verbundenen Verschränkungskeil. 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. Komplexität und Verschränkung in nicht-lokaler Berechnung und Holographie. 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 für allgemeine Zugangsstrukturen. 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. Die Large-N-Grenze superkonformer Feldtheorien und Supergravitation. Internationale Zeitschrift für Theoretische Physik, 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-Raum und Holographie. 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. Theorie des Quantengeheimnisses. 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 und Michael A. Nielsen. Quantendatenverarbeitung und Fehlerkorrektur. 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 und Michael D. Westmoreland. Ungefähre Quantenfehlerkorrektur. 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 und Christoph Meinel. Struktur und Bedeutung der Logspace-Mod-Klasse. Mathematische Systemtheorie, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer und Avi Wigderson. Auf Span-Programme. In [1993] Proceedings of the Eight Annual Structure in Complexity Theory Conference, Seiten 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neil D. Jones, Y. Edmund Lien und William T. Laaser. Neue Probleme für nichtdeterministischen Protokollspeicherplatz abgeschlossen. Mathematische Systemtheorie, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt und Eric Allender. Nichtdeterminismus eindeutig machen. 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 und Shiyu Zhou. Isolierung, Zuordnung und Zählung einheitlicher und ungleichmäßiger Obergrenzen. 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. Kommunikationskomplexität. In Advances in Computers, Band 44, Seiten 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. Die Kommunikationskomplexität von Schwellengattern. Combinatorics, Paul Erdos is Eighty, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman und Stephen A Cook. Exponentielle Untergrenzen für monotone Spannenprogramme. Im Jahr 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Seiten 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Sofortige nicht-lokale Berechnung von Quantenschaltungen mit geringer T-Tiefe. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), Band 61 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 9:1–9:24, Dagstuhl, Deutschland, 2016. Schloss Dagstuhl–Leibniz- Zentrum für Informatik. ISBN 978-3-95977-019-4. 10.4230/​LIPIcs.TQC.2016.9.
https: // doi.org/ 10.4230 / LIPIcs.TQC.2016.9

Zitiert von

[1] Alex May, „Komplexität und Verschränkung in nicht-lokaler Berechnung und Holographie“, Quantum 6, 864 (2022).

[2] Alex May, Jonathan Sorce und Beni Yoshida, „Der Theorem des verbundenen Keils und seine Konsequenzen“, Zeitschrift für Hochenergiephysik 2022 11, 153 (2022).

[3] Kfir Dolev und Sam Cree, „Holographie als Ressource für nichtlokale Quantenberechnung“, arXiv: 2210.13500, (2022).

[4] Kfir Dolev und Sam Cree, „Nichtlokale Berechnung von Quantenschaltkreisen mit kleinen Lichtkegeln“, arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman und Philip Verduyn Lunel, „Beziehung nichtlokaler Quantenberechnung zur informationstheoretischen Kryptographie“, arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs und Florian Speelman, „Einzel-Qubit-verlusttolerantes Quantenpositionsverifizierungsprotokoll sicher gegen verwickelte Angreifer“, arXiv: 2212.03674, (2022).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 08:10:03 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-08-10 03:31:41).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal