Code-routing: en ny attack mot positionsverifiering

Code-routing: en ny attack mot positionsverifiering

Tidsstämpel: 9 augusti 2023 11:18
Code-routing: en ny attack mot positionsverifiering PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Joy Cree och Alex May

Stanford University

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Den kryptografiska uppgiften med positionsverifiering försöker verifiera en parts position i rymdtid genom att utnyttja begränsningar för kvantinformation och relativistisk kausalitet. Ett populärt verifieringsschema känt som $f$-routing innebär att provaren måste omdirigera ett kvantsystem baserat på värdet av en boolesk funktion $f$. Fuskstrategier för $f$-routing-schemat kräver att provaren använder fördelad entanglement, och säkerheten för systemet vilar på antaganden om hur mycket entanglement en prover kan manipulera. Här ger vi en ny fuskstrategi där kvantsystemet är kodat till ett hemlighetsdelningsschema, och auktoriseringsstrukturen för hemlighetsdelningsschemat utnyttjas för att styra systemet på lämpligt sätt. Denna strategi slutför $f$-routinguppgiften med $O(SP_p(f))$ EPR-par, där $SP_p(f)$ är den minimala storleken på ett spanprogram över fältet $mathbb{Z}_p$ som beräknar $ f$. Detta visar att vi effektivt kan attackera $f$-routingscheman när $f$ är i komplexitetsklassen $text{Mod}_ptext{L}$, efter att ha tillåtit lokal förbearbetning. Den bästa tidigare konstruktionen uppnådde klassen L, som tros vara strikt inom $text{Mod}_ptext{L}$. Vi visar också att storleken på ett kvanthemlighetsdelningsschema med indikatorfunktion $f_I$ övre gränser för entanglement kostnaden för $f$-routing på funktionen $f_I$.

► BibTeX-data

► Referenser

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty och Rafail Ostrovsky. Positionsbaserad kryptografi. I Annual International Cryptology Conference, sidorna 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 och Timothy P Spiller. Kvanttaggning: Autentisering av plats via kvantinformation och relativistiska signaleringsbegränsningar. 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. Kvantuppgifter i Minkowski rymden. 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 och Wojciech H Zurek. Ett enda kvantum kan inte klonas. 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 och Raymond G Beausoleil. Taggningssystem, 11 juli 2006. US patent 7,075,438 XNUMX XNUMX.

[6] Robert A Malaney. Platsberoende kommunikation med hjälp av kvantintrång. 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 och Christian Schaffner. Positionsbaserad kvantkryptografi: Omöjlighet och konstruktioner. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi och Robert König. Förenklad momentan icke-lokal kvantberäkning med applikationer för positionsbaserad kryptografi. 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 och Florian Speelman. Ett protokoll för positionsverifiering med en qubit som är säkert mot multi-qubit-attacker. Nature Physics, sidorna 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 och Florian Speelman. Trädgårdsslangmodellen. I Proceedings of the 4th conference on Innovations in Theoretical Computer Science, sidorna 145–158, 2013. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck och Supartha Podder. Nya gränser för trädgårdsslangmodellen. 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 och Supartha Podder. Kommunikationsminne: Minneslös kommunikationskomplexitet. I 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. Kvantuppgifter i holografi. 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 och Jonathan Sorce. Holografisk spridning kräver en ansluten intrasslingskil. 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. Komplexitet och förveckling i icke-lokal beräkning och holografi. 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. Kvanthemlighetsdelning för allmänna åtkomststrukturer. 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: kvant-ph / 0001087

[17] Juan Maldacena. Den stora N-gränsen för superkonforma fältteorier och supergravitation. 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 utrymme och holografi. 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. Teori om kvanthemlighetsdelning. 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 och Michael A Nielsen. Kvantdatabehandling och felkorrigering. 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 och Michael D Westmoreland. Ungefärlig kvantfelskorrigering. 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 och Christoph Meinel. Struktur och betydelse för logspace-mod-klassen. Mathematical systems theory, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer och Avi Wigderson. På span-program. I [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, sidorna 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien och William T Laaser. Nya problem slutförda för icke-deterministiskt loggutrymme. Matematisk systemteori, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt och Eric Allender. Att göra icke-determinism entydig. 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 och Shiyu Zhou. Isolering, matchning och räkning av enhetliga och olikformiga övre gränser. 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. Kommunikationskomplexitet. I Advances in Computers, volym 44, sidorna 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. Kommunikationskomplexiteten hos tröskelgrindar. Combinatorics, Paul Erdos är åttio, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman och Stephen A Cook. Exponentiella nedre gränser för monotona spännprogram. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), sidorna 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Momentan icke-lokal beräkning av låga T-djupa kvantkretsar. I 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volym 61 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 9:1–9:24, Dagstuhl, Tyskland, 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

Citerad av

[1] Alex May, "Komplexitet och förveckling i icke-lokal beräkning och holografi", Quantum 6, 864 (2022).

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

[3] Kfir Dolev och Sam Cree, "Holografi som en resurs för icke-lokal kvantberäkning", arXiv: 2210.13500, (2022).

[4] Kfir Dolev och Sam Cree, "Icke-lokal beräkning av kvantkretsar med små ljuskoner", arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman och Philip Verduyn Lunel, "Relaterar icke-lokal kvantberäkning till informationsteoretisk kryptografi", arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs och Florian Speelman, "Single-qubit förlusttolerant kvantpositionsverifieringsprotokoll säkert mot intrasslade angripare", arXiv: 2212.03674, (2022).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-08-10 03:31:42). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2023-08-10 03:31:41).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal