Coderoutering: een nieuwe aanval op positieverificatie

Coderoutering: een nieuwe aanval op positieverificatie

Tijdstempel: 9 augustus 2023 11:18 uur
Coderouting: een nieuwe aanval op positieverificatie PlatoBlockchain Data Intelligence. Verticaal zoeken. Ai.

Vreugde Cree en Alex mei

Stanford University

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

De cryptografische taak van positieverificatie probeert de locatie van een partij in de ruimtetijd te verifiëren door gebruik te maken van beperkingen op kwantuminformatie en relativistische causaliteit. Een populair verificatieschema dat bekend staat als $f$-routing houdt in dat de bewijzer een kwantumsysteem moet omleiden op basis van de waarde van een Booleaanse functie $f$. Valsspeelstrategieën voor het $f$-routeringsschema vereisen dat de bewijzer vooraf gedeelde verstrengeling gebruikt, en de veiligheid van het schema berust op aannames over hoeveel verstrengeling een bewijzer kan manipuleren. Hier geven we een nieuwe cheat-strategie waarbij het kwantumsysteem wordt gecodeerd in een schema voor het delen van geheimen, en de autorisatiestructuur van het schema voor het delen van geheimen wordt uitgebuit om het systeem op de juiste manier te sturen. Deze strategie voltooit de $f$-routeringstaak met behulp van $O(SP_p(f))$ EPR-paren, waarbij $SP_p(f)$ de minimale grootte is van een spanprogramma over het veld $mathbb{Z}_p$ computing $ f$. Dit laat zien dat we $f$-routeringsschema's efficiënt kunnen aanvallen wanneer $f$ zich in de complexiteitsklasse $text{Mod}_ptext{L}$ bevindt, nadat lokale voorverwerking is toegestaan. De beste eerdere constructie bereikte de klasse L, waarvan wordt aangenomen dat deze strikt binnen $text{Mod}_ptext{L}$ valt. We laten ook zien dat de omvang van een schema voor het delen van kwantumgeheimen met indicatorfunctie $f_I$ de bovengrenzen van de verstrengelingskosten van $f$-routing op de functie $f_I$ beïnvloedt.

► BibTeX-gegevens

► Referenties

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty en Rafail Ostrovsky. Positiegebaseerde cryptografie. In de jaarlijkse internationale cryptologieconferentie, pagina's 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 en Timothy P Spiller. Kwantumtagging: locatieverificatie via kwantuminformatie en relativistische signaleringsbeperkingen. Fysieke beoordeling A, 84 (1): 012326, 2011. https://​/​doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Adriaan Kent. Kwantumtaken in de Minkowski-ruimte. Klassieke en kwantumzwaartekracht, 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 en Wojciech H Zurek. Eén enkel kwantum kan niet worden gekloond. 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 en Raymond G Beausoleil. Tagging-systemen, 11 juli 2006. Amerikaans octrooi 7,075,438.

[6] Robert A Malaney. Locatieafhankelijke communicatie met behulp van kwantumverstrengeling. Fysieke beoordeling 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 en Christian Schaffner. Positiegebaseerde kwantumcryptografie: onmogelijkheid en constructies. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi en Robert König. Vereenvoudigde onmiddellijke niet-lokale kwantumberekening met toepassingen voor op positie gebaseerde cryptografie. 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 en Florian Speelman. Een positieverificatieprotocol met één qubit dat beveiligd is tegen aanvallen met meerdere qubits. Natuurfysica, pagina's 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 en Florian Speelman. Het tuinslangmodel. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pagina's 145–158, 2013. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck en Supartha Podder. Nieuwe grenzen voor het tuinslangmodel. 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 en Supartha Podder. Communicatieherinnering: geheugenloze communicatiecomplexiteit. Op de 12e 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 mei. Kwantumtaken in holografie. 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 en Jonathan Sorce. Holografische verstrooiing vereist een verbonden verstrengelingswig. 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 Mei. Complexiteit en verstrengeling in niet-lokale berekeningen en holografie. 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. Delen van kwantumgeheimen voor algemene toegangsstructuren. 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. De grote N-limiet van superconforme veldtheorieën en superzwaartekracht. Internationaal tijdschrift voor theoretische natuurkunde, 38 (4): 1113–1133, 1999. https://​/​doi.org/​10.1023/​A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] Eduard Witten. Anti-de-sitterruimte en holografie. 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] Daniël Gottesman. Theorie van het delen van kwantumgeheimen. Fysieke beoordeling A, 61 (4): 042311, 2000. https://​/​doi.org/​10.1103/​PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Benjamin Schumacher en Michael A Nielsen. Kwantumgegevensverwerking en foutcorrectie. Fysieke beoordeling A, 54 (4): 2629, 1996. https://​/​doi.org/​10.1103/​PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] Benjamin Schumacher en Michael D Westmoreland. Geschatte kwantumfoutcorrectie. 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 en Christoph Meinel. Structuur en belang van de logspace-mod-klasse. Wiskundige systeemtheorie, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer en Avi Wigderson. Op spanprogramma's. In [1993] Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pagina's 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien en William T Laaser. Nieuwe problemen voltooid voor niet-deterministische logruimte. Wiskundige systeemtheorie, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt en Eric Allender. Non-determinisme ondubbelzinnig maken. 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 en Shiyu Zhou. Isoleren, matchen en tellen van uniforme en niet-uniforme bovengrenzen. 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. Communicatie complexiteit. In Advances in Computers, deel 44, pagina's 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. De communicatiecomplexiteit van drempelpoorten. Combinatoriek, Paul Erdos is Tachtig, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman en Stephen A Cook. Exponentiële ondergrenzen voor monotone spanprogramma's. In 2016 IEEE 57e jaarlijkse symposium over de grondslagen van computerwetenschappen (FOCS), pagina's 406–415. IEEE, 2016. 10.1109/FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Onmiddellijke niet-lokale berekening van kwantumcircuits met lage T-diepte. In de 11e conferentie over de theorie van kwantumcomputers, communicatie en cryptografie (TQC 2016), deel 61 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 9:1–9:24, Dagstuhl, Duitsland, 2016. Schloss Dagstuhl–Leibniz- Centrum voor Informatik. ISBN 978-3-95977-019-4. 10.4230/​LIPIcs.TQC.2016.9.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2016.9

Geciteerd door

[1] Alex May, “Complexiteit en verstrengeling in niet-lokale berekeningen en holografie”, Kwantum 6, 864 (2022).

[2] Alex May, Jonathan Sorce en Beni Yoshida, "De verbonden wigstelling en de gevolgen daarvan", Tijdschrift voor Hoge Energiefysica 2022 11, 153 (2022).

[3] Kfir Dolev en Sam Cree, "Holografie als hulpmiddel voor niet-lokale kwantumberekening", arXiv: 2210.13500, (2022).

[4] Kfir Dolev en Sam Cree, "Niet-lokale berekening van kwantumcircuits met kleine lichtkegels", arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman en Philip Verduyn Lunel, "Niet-lokale kwantumberekeningen relateren aan informatietheoretische cryptografie", arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs en Florian Speelman, "Single-qubit verliestolerant kwantumpositieverificatieprotocol beveiligd tegen verstrikte aanvallers", arXiv: 2212.03674, (2022).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-08-10 03:31:42). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-08-10 03:31:41).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Tijdstempel:

Meer van Quantum Journaal