Koderouting: et nytt angrep på posisjonsverifisering

Koderouting: et nytt angrep på posisjonsverifisering

Tidsstempel: 9. august 2023 kl.11: 18
Koderouting: et nytt angrep på posisjonsverifisering PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Joy Cree og Alex May

Stanford University

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Den kryptografiske oppgaven med posisjonsverifisering forsøker å verifisere en parts plassering i romtid ved å utnytte begrensninger på kvanteinformasjon og relativistisk kausalitet. Et populært verifiseringsskjema kjent som $f$-ruting innebærer å kreve at beviseren omdirigerer et kvantesystem basert på verdien av en boolsk funksjon $f$. Juksestrategier for $f$-rutingsskjemaet krever at beviseren bruker forhåndsdelt sammenfiltring, og sikkerheten til opplegget hviler på antakelser om hvor mye sammenfiltring en bevisst kan manipulere. Her gir vi en ny juksestrategi der kvantesystemet er kodet inn i et hemmeligdelingsskjema, og autorisasjonsstrukturen til hemmeligdelingsskjemaet blir utnyttet for å styre systemet riktig. Denne strategien fullfører $f$-rutingsoppgaven ved å bruke $O(SP_p(f))$ EPR-par, der $SP_p(f)$ er den minimale størrelsen på et spennprogram over feltet $mathbb{Z}_p$ som beregner $ f$. Dette viser at vi effektivt kan angripe $f$-rutingsopplegg når $f$ er i kompleksitetsklassen $text{Mod}_ptext{L}$, etter å ha tillatt lokal forhåndsbehandling. Den beste tidligere konstruksjonen oppnådde klassen L, som antas å være innenfor $text{Mod}_ptext{L}$. Vi viser også at størrelsen på et kvantehemmelig delingsskjema med indikatorfunksjon $f_I$ øvre grenser for sammenfiltringskostnaden for $f$-ruting på funksjonen $f_I$.

► BibTeX-data

► Referanser

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty og Rafail Ostrovsky. Posisjonsbasert kryptografi. I den årlige internasjonale kryptologikonferansen, side 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 og Timothy P Spiller. Kvantemerking: Autentisering av plassering via kvanteinformasjon og relativistiske signalbegrensninger. 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. Kvanteoppgaver i Minkowski-rommet. 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 og Wojciech H Zurek. Et enkelt kvante kan ikke klones. 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 og Raymond G Beausoleil. Merkesystemer, 11. juli 2006. US patent 7,075,438.

[6] Robert A Malaney. Stedsavhengig kommunikasjon ved bruk av kvanteforviklinger. 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 og Christian Schaffner. Posisjonsbasert kvantekryptografi: Umulighet og konstruksjoner. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi og Robert König. Forenklet øyeblikkelig ikke-lokal kvanteberegning med applikasjoner til posisjonsbasert 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 og Florian Speelman. En enkelt-qubit-posisjonsverifiseringsprotokoll som er sikker mot multi-qubit-angrep. Nature Physics, side 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 og Florian Speelman. Hageslangemodellen. I Proceedings of the 4th conference on Innovations in Theoretical Computer Science, side 145–158, 2013. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck og Supartha Podder. Nye grenser for hageslangemodellen. 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 og Supartha Podder. Kommunikasjonsminne: Minneløs kommunikasjonskompleksitet. 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. Kvanteoppgaver 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 og Jonathan Sorce. Holografisk spredning krever en tilkoblet sammenfiltringskile. 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. Kompleksitet og sammenfiltring i ikke-lokal beregning og 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. Kvantehemmelig deling for generelle tilgangsstrukturer. 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. Den store N-grensen for superkonforme feltteorier og supergravitasjon. 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 plass og 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 kvantehemmelig deling. Fysisk gjennomgang A, 61 (4): 042311, 2000. https: / / doi.org/ 10.1103 / PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Benjamin Schumacher og Michael A Nielsen. Kvantedatabehandling og feilretting. 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 og Michael D Westmoreland. Omtrentlig kvantefeilkorreksjon. 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 og Christoph Meinel. Struktur og betydning av logspace-mod-klassen. Matematisk systemteori, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

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

[24] Neil D Jones, Y Edmund Lien og William T Laaser. Nye problemer fullført for ikke-deterministisk loggplass. Matematisk systemteori, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt og Eric Allender. Gjør ikke-determinisme 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 og Shiyu Zhou. Isolering, matching og telling av uniforme og uensartede øvre grenser. 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. Kommunikasjonskompleksitet. I Advances in Computers, bind 44, side 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. Kommunikasjonskompleksiteten til terskelporter. Combinatorics, Paul Erdos er åtti, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman og Stephen A Cook. Eksponentielle nedre grenser for monotone spennprogrammer. I 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), side 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Øyeblikkelig ikke-lokal beregning av kvantekretser med lav T-dybde. I 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), bind 61 av Leibniz International Proceedings in Informatics (LIPIcs), side 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

Sitert av

[1] Alex May, "Kompleksitet og sammenfiltring i ikke-lokal beregning og holografi", Quantum 6, 864 (2022).

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

[3] Kfir Dolev og Sam Cree, "Holografi som en ressurs for ikke-lokal kvanteberegning", arxiv: 2210.13500, (2022).

[4] Kfir Dolev og Sam Cree, "Ikke-lokal beregning av kvantekretser med små lyskjegler", arxiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman og Philip Verduyn Lunel, "Relatering av ikke-lokal kvanteberegning til informasjonsteoretisk kryptografi", arxiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs og Florian Speelman, "Enkelt-qubit tapstolerant kvanteposisjonsverifiseringsprotokoll sikret mot sammenfiltrede angripere", arxiv: 2212.03674, (2022).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-08-10 03:31:42). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2023-08-10 03:31:41).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal