Routing kodu: nowy atak na weryfikację pozycji

Routing kodu: nowy atak na weryfikację pozycji

Znacznik czasu: 9 sierpnia 2023 11:18
Code-routing: nowy atak na weryfikację pozycji PlatoBlockchain Data Intelligence. Wyszukiwanie pionowe. AI.

Radość Cree i Aleks Maj

Stanford University

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Kryptograficzne zadanie weryfikacji pozycji ma na celu zweryfikowanie lokalizacji jednej ze stron w czasoprzestrzeni poprzez wykorzystanie ograniczeń informacji kwantowej i relatywistycznej przyczynowości. Popularny schemat weryfikacji, znany jako $f$-routing, polega na wymaganiu od weryfikatora przekierowania systemu kwantowego na podstawie wartości funkcji boolowskiej $f$. Strategie oszukiwania dla schematu $f$-routing wymagają, aby dowodzący używał wstępnie udostępnionego splątania, a bezpieczeństwo schematu opiera się na założeniach dotyczących tego, jak dużym splątaniem może manipulować dowodzący. Tutaj podajemy nową strategię oszukiwania, w której system kwantowy jest zakodowany w schemacie udostępniania tajemnic, a struktura autoryzacji schematu udostępniania tajemnic jest wykorzystywana do odpowiedniego kierowania systemem. Strategia ta kończy zadanie $f$-routingu przy użyciu $O(SP_p(f))$ par EPR, gdzie $SP_p(f)$ jest minimalnym rozmiarem programu span w polu $mathbb{Z}_p$ obliczenie $ f $. Pokazuje to, że możemy skutecznie atakować schematy routingu $f$, ilekroć $f$ należy do klasy złożoności $text{Mod}_ptext{L}$, po uwzględnieniu lokalnego przetwarzania wstępnego. Najlepsza wcześniejsza konstrukcja osiągnęła klasę L, która, jak się uważa, mieści się ściśle w $text{Mod}_ptext{L}$. Pokazujemy również, że rozmiar schematu współdzielenia sekretów kwantowych z funkcją wskaźnika $f_I$ ogranicza górne granice kosztu splątania $f$-routingu na funkcji $f_I$.

► Dane BibTeX

► Referencje

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty i Rafail Ostrovsky. Kryptografia oparta na pozycji. W Annual International Cryptology Conference, strony 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 i Timothy P. Spiller. Znakowanie kwantowe: Uwierzytelnianie lokalizacji za pomocą informacji kwantowej i relatywistycznych ograniczeń sygnalizacyjnych. Przegląd fizyczny A, 84 (1): 012326, 2011. https://​/​doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Adriana Kenta. Zadania kwantowe w przestrzeni Minkowskiego. Grawitacja klasyczna i kwantowa, 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 i Wojciech H. Żurek. Pojedynczego kwantu nie da się sklonować. 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 i Raymond G. Beausoleil. Systemy znakowania, 11 lipca 2006. Patent US 7,075,438.

[6] Roberta Malaneya. Komunikacja zależna od lokalizacji z wykorzystaniem splątania kwantowego. Przegląd fizyczny 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 i Christian Schaffner. Kryptografia kwantowa oparta na pozycji: niemożliwość i konstrukcje . SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salmana Beigiego i Roberta Königa. Uproszczone natychmiastowe nielokalne obliczenia kwantowe z aplikacjami do kryptografii opartej na pozycji. 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 i Florian Speelman. Protokół weryfikacji pozycji z jednym kubitem, który jest zabezpieczony przed atakami z wykorzystaniem wielu kubitów. Nature Physics, strony 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 i Florian Speelman. Model węża ogrodowego. W Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, s. 145–158, 2013. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck i Supartha Podder. Nowe granice dla modelu węża ogrodowego. W Podstawy technologii oprogramowania i informatyki teoretycznej, 2014. 10.4230/​LIPIcs.FSTTCS.2014.481.
https://​/​doi.org/​10.4230/​LIPics.FSTTCS.2014.481

[12] Srinivasan Arunachalam i Supartha Podder. Pamiątka z komunikacji: złożoność komunikacji bez pamięci. W 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] Aleks Maj. Zadania kwantowe w holografii. 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 i Jonathan Sorce. Rozpraszanie holograficzne wymaga połączonego klina splątania. 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] Aleks Maj. Złożoność i uwikłanie w nielokalne obliczenia i holografię. Quantum, 6: 864, listopad 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] Adama D Smitha. Udostępnianie tajnych danych kwantowych dla struktur ogólnego dostępu. 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] Juana Maldaceny. Granica dużego N superkonformalnych teorii pola i supergrawitacji. Międzynarodowy dziennik fizyki teoretycznej, 38 (4): 1113–1133, 1999. https://​/​doi.org/​10.1023/​A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] Edwarda Wittena. Przestrzeń anty-de sitter i holografia. Postępy w fizyce teoretycznej i matematycznej, 2: 253–291, 1998. 10.4310/​ATMP.1998.v2.n2.a2.
https:/​/​doi.org/​10.4310/​ATMP.1998.v2.n2.a2

[19] Daniela Gottesmana. Teoria udostępniania tajemnic kwantowych. Przegląd fizyczny A, 61 (4): 042311, 2000. https:/​/​doi.org/​10.1103/​PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Benjamina Schumachera i Michaela A Nielsena. Kwantowe przetwarzanie danych i korekcja błędów. Przegląd fizyczny A, 54 (4): 2629, 1996. https://​/​doi.org/​10.1103/​PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] Benjamina Schumachera i Michaela D. Westmorelanda. Przybliżona korekcja błędów kwantowych. Quantum Information Processing, 1 (1): 5–12, 2002. https://​/​doi.org/​10.1023/​A:1019653202562.
https: / / doi.org/ 10.1023 / A: 1019653202562

[22] Gerharda Buntrocka, Carstena Damma, Ulricha Hertrampfa i Christopha Meinela. Struktura i znaczenie klasy logspace-mod. Teoria systemów matematycznych, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmera i Aviego Wigdersona. W programach rozpiętościowych. W [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, strony 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neila D. Jonesa, Y. Edmunda Liena i Williama T. Laasera. Ukończono nowe problemy dla niedeterministycznej przestrzeni logów. Teoria systemów matematycznych, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klausa Reinhardta i Erica Allendera. Jednoznaczność niedeterminizmu. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https://​/​doi.org/​10.1137/​S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

[26] Erica Allendera, Klausa Reinhardta i Shiyu Zhou. Izolowanie, dopasowywanie i liczenie jednorodnych i niejednorodnych górnych granic. 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. Złożoność komunikacji. W Advances in Computers, tom 44, strony 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. Złożoność komunikacyjna bramek progowych. Kombinatoryka, Paul Erdos ma osiemdziesiąt lat, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman i Stephen A Cook. Wykładnicze dolne granice dla programów o rozpiętości monotonicznej. W 2016 r. IEEE 57. doroczne sympozjum na temat podstaw informatyki (FOCS), strony 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Floriana Speelmana. Natychmiastowe nielokalne obliczenia obwodów kwantowych o niskiej głębokości T. W 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), tom 61 Leibniz International Proceedings in Informatics (LIPIcs), strony 9:1–9:24, Dagstuhl, Niemcy, 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

Cytowany przez

[1] Alex May, „Złożoność i uwikłanie w nielokalne obliczenia i holografię”, Kwant 6, 864 (2022).

[2] Alex May, Jonathan Sorce i Beni Yoshida, „Twierdzenie połączonego klina i jego konsekwencje”, Journal of High Energy Physics 2022 11, 153 (2022).

[3] Kfir Dolev i Sam Cree, „Holografia jako źródło nielokalnych obliczeń kwantowych”, arXiv: 2210.13500, (2022).

[4] Kfir Dolev i Sam Cree, „Nielokalne obliczenia obwodów kwantowych z małymi stożkami światła”, arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman i Philip Verduyn Lunel, „Odnoszenie nielokalnych obliczeń kwantowych do kryptografii teorii informacji”, arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs i Florian Speelman, „Protokół weryfikacji pozycji kwantowej z tolerancją na straty pojedynczego kubitu, bezpieczny przed splątanymi atakującymi”, arXiv: 2212.03674, (2022).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2023-08-10 03:31:42). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2023-08-10 03:31:41).

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy