Usmerjanje kode: nov napad na preverjanje položaja

Usmerjanje kode: nov napad na preverjanje položaja

Časovni žig: 9. avgust 2023 11:18
Code-routing: a new attack on position verification PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Joy Cree in Alex May

Univerza Stanford

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Kriptografska naloga preverjanja položaja poskuša preveriti lokacijo ene stranke v prostor-času z izkoriščanjem omejitev kvantnih informacij in relativistične vzročnosti. Priljubljena shema preverjanja, znana kot $f$-usmerjanje, vključuje zahtevo, da dokazovalnik preusmeri kvantni sistem na podlagi vrednosti logične funkcije $f$. Strategije goljufanja za $f$-usmerjevalno shemo zahtevajo, da dokazovalnik uporablja predhodno deljeno zapletenost, varnost sheme pa temelji na predpostavkah o tem, koliko zapletenosti lahko preverjalec manipulira. Tukaj podajamo novo strategijo goljufanja, v kateri je kvantni sistem kodiran v shemo za deljenje skrivnosti, avtorizacijska struktura sheme za deljenje skrivnosti pa se izkorišča za ustrezno usmerjanje sistema. Ta strategija dokonča nalogo usmerjanja $f$ z uporabo parov EPR $O(SP_p(f))$, kjer je $SP_p(f)$ minimalna velikost razponskega programa nad poljem $mathbb{Z}_p$, ki izračuna $ f$. To kaže, da lahko učinkovito napademo $f$-usmerjevalne sheme, kadar koli je $f$ v kompleksnem razredu $text{Mod}_ptext{L}$, potem ko omogočimo lokalno predprocesiranje. Najboljša prejšnja konstrukcija je dosegla razred L, za katerega se domneva, da je strogo znotraj $text{Mod}_ptext{L}$. Pokažemo tudi, da velikost sheme za deljenje kvantnih skrivnosti z indikatorsko funkcijo $f_I$ zgornjo mejo zapletanja stroškov $f$-usmerjanja na funkciji $f_I$.

► BibTeX podatki

► Reference

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty in Rafail Ostrovsky. Kriptografija na podlagi položaja. Na letni mednarodni kriptološki konferenci, strani 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 in Timothy P. Spiller. Kvantno označevanje: avtentikacija lokacije prek kvantnih informacij in relativističnih signalnih omejitev. 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. Kvantne naloge v prostoru Minkowskega. Klasična in kvantna gravitacija, 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 in Wojciech H Zurek. Enega kvanta ni mogoče klonirati. Narava, 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 in Raymond G Beausoleil. Sistemi označevanja, 11. julij 2006. Patent ZDA 7,075,438.

[6] Robert A Malaney. Lokacijsko odvisne komunikacije z uporabo kvantne prepletenosti. 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 Ostrovski in Christian Schaffner. Pozicijska kvantna kriptografija: nezmožnost in konstrukcije. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi in Robert König. Poenostavljeno trenutno nelokalno kvantno računanje z aplikacijami za kriptografijo na podlagi položaja. 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 in Florian Speelman. Protokol za preverjanje položaja z enim kubitom, ki je varen pred napadi z več kubiti. Nature Physics, strani 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 in Florian Speelman. Model vrtne cevi. V zborniku 4. konference o inovacijah v teoretični računalniški znanosti, strani 145–158, 2013. https:/​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck in Supartha Podder. Nove meje za model vrtne cevi. V Fundations 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 in Supartha Podder. Spomin na komunikacijo: Kompleksnost komunikacije brez spomina. Na 12. konferenci o inovacijah v teoretični računalniški znanosti (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. Kvantne naloge v holografiji. 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 in Jonathan Sorce. Holografsko sipanje zahteva povezan zapletni klin. 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. Kompleksnost in zapletenost v nelokalnem računanju in holografiji. 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. Kvantna delitev skrivnosti za splošne dostopne strukture. arXiv prednatis 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. Meja velikega N superkonformnih teorij polja in supergravitacije. 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 prostor in holografija. 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. Teorija delitve kvantne skrivnosti. 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 in Michael A Nielsen. Kvantna obdelava podatkov in odpravljanje napak. 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 in Michael D Westmoreland. Približna kvantna korekcija napake. Kvantna obdelava informacij, 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 in Christoph Meinel. Struktura in pomen razreda logspace-mod. Teorija matematičnih sistemov, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer in Avi Wigderson. Na span programih. V [1993] Zbornik osme letne konference o strukturi teorije kompleksnosti, strani 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https://​/​doi.org/​10.1109/​SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien in William T Laaser. Nove težave so dokončane za nedeterministični prostor dnevnika. Teorija matematičnih sistemov, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt in Eric Allender. Narediti nedeterminizem nedvoumen. 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 in Shiyu Zhou. Izolacija, ujemanje in štetje enotnih in neenotnih zgornjih meja. 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. Kompleksnost komunikacije. V Napredek v računalnikih, zvezek 44, strani 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. Komunikacijska kompleksnost pragovnih vrat. Kombinatorika, Paul Erdos ima osemdeset let, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman in Stephen A Cook. Eksponentne spodnje meje za programe monotonega razpona. Leta 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), strani 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Takojšnje nelokalno računanje kvantnih vezij z nizko T-globino. Na 11. konferenci o teoriji kvantnega računalništva, komunikacije in kriptografije (TQC 2016), zvezek 61 Leibniz International Proceedings in Informatics (LIPIcs), strani 9:1–9:24, Dagstuhl, Nemčija, 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

Navedel

[1] Alex May, "Zapletenost in zapletenost v nelokalnem računanju in holografiji", Kvant 6, 864 (2022).

[2] Alex May, Jonathan Sorce in Beni Yoshida, "Teorem povezanega klina in njegove posledice", Journal of High Energy Physics 2022 11, 153 (2022).

[3] Kfir Dolev in Sam Cree, "Holografija kot vir za nelokalno kvantno računanje", arXiv: 2210.13500, (2022).

[4] Kfir Dolev in Sam Cree, "Nelokalno računanje kvantnih vezij z majhnimi svetlobnimi stožci", arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman in Philip Verduyn Lunel, "Povezava nelokalnega kvantnega računanja z informacijsko teoretično kriptografijo", arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs in Florian Speelman, »Protokol kvantnega preverjanja položaja, odporen na posamezne kubitne izgube, varen pred zapletenimi napadalci« arXiv: 2212.03674, (2022).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2023-08-10 03:31:42). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2023-08-10 03:31:41).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal