Perutean kode: serangan baru pada verifikasi posisi

Perutean kode: serangan baru pada verifikasi posisi

Stempel Waktu: 9 Agustus 2023 11
Perutean kode: serangan baru terhadap verifikasi posisi Intelijen Data PlatoBlockchain. Pencarian Vertikal. Ai.

Joy Cree dan Alex Mei

Stanford University

Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.

Abstrak

Tugas kriptografi verifikasi posisi berupaya memverifikasi lokasi satu pihak dalam ruangwaktu dengan mengeksploitasi kendala pada informasi kuantum dan kausalitas relativistik. Skema verifikasi populer yang dikenal sebagai $f$-routing mengharuskan pembukti untuk mengarahkan ulang sistem kuantum berdasarkan nilai fungsi Boolean $f$. Strategi curang untuk skema $f$-routing mengharuskan pembukti menggunakan keterikatan yang dibagikan sebelumnya, dan keamanan skema bertumpu pada asumsi tentang berapa banyak keterikatan yang dapat dimanipulasi oleh pembukti. Di sini, kami memberikan strategi curang baru di mana sistem kuantum dikodekan ke dalam skema pembagian rahasia, dan struktur otorisasi skema pembagian rahasia dieksploitasi untuk mengarahkan sistem dengan tepat. Strategi ini menyelesaikan tugas perutean $f$ menggunakan $O(SP_p(f))$ pasangan EPR, di mana $SP_p(f)$ adalah ukuran minimal program span di atas bidang $mathbb{Z}_p$ menghitung $ f$. Ini menunjukkan bahwa kita dapat secara efisien menyerang skema perutean $f$ setiap kali $f$ berada di kelas kompleksitas $text{Mod}_ptext{L}$, setelah mengizinkan pra-pemrosesan lokal. Konstruksi terbaik sebelumnya mencapai kelas L, yang diyakini benar-benar berada di dalam $text{Mod}_ptext{L}$. Kami juga menunjukkan bahwa ukuran skema berbagi rahasia kuantum dengan fungsi indikator $f_I$ batas atas biaya keterikatan $f$-routing pada fungsi $f_I$.

► data BibTeX

► Referensi

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, dan Rafail Ostrovsky. Kriptografi berbasis posisi. Dalam Konferensi Kriptologi Internasional Tahunan, halaman 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, dan Timothy P Spiller. Penandaan kuantum: Otentikasi lokasi melalui informasi kuantum dan kendala pensinyalan relativistik. Tinjauan Fisik A, 84 (1): 012326, 2011. https://​/​doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Adrian Kent. Tugas kuantum di ruang Minkowski. Gravitasi Klasik dan Kuantum, 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 dan Wojciech H Zurek. Kuantum tunggal tidak dapat dikloning. Alam, 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, and Raymond G Beausoleil. Sistem penandaan, 11 Juli 2006. Paten AS 7,075,438.

[6] Robert A Malaney. Komunikasi yang bergantung pada lokasi menggunakan keterikatan kuantum. Tinjauan Fisik 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, and Christian Schaffner. Kriptografi kuantum berbasis posisi: Ketidakmungkinan dan konstruksi. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/10.1137/130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi dan Robert Konig. Komputasi kuantum non-lokal instan yang disederhanakan dengan aplikasi untuk kriptografi berbasis posisi. Jurnal Fisika Baru, 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, dan Florian Speelman. Protokol verifikasi posisi qubit tunggal yang aman terhadap serangan multi-qubit. Fisika Alam, halaman 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, dan Florian Speelman. Model selang taman. Dalam Prosiding konferensi ke-4 tentang Inovasi dalam Ilmu Komputer Teoritis, halaman 145–158, 2013. https://doi.org/10.1145/2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck dan Supartha Podder. Batasan baru untuk model selang taman. Dalam 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 dan Supartha Podder. Kenang-kenangan komunikasi: Kompleksitas komunikasi tanpa memori. Dalam Inovasi ke-12 dalam Konferensi Ilmu Komputer Teoritis (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum untuk Informatik, 2021. 10.4230/​LIPIcs.ITCS.2021.61.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.61

[13] Alex May. Tugas kuantum dalam holografi. Jurnal Fisika Energi Tinggi, 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, dan Jonathan Sorce. Hamburan holografik membutuhkan baji keterikatan yang terhubung. Jurnal Fisika Energi Tinggi, 2020 (8): 1–34, 2020. https://​/​doi.org/​10.1007/​JHEP08(2020)132.
https: / / doi.org/ 10.1007 / JHEP08 (2020) 132

[15] Alex May. Kompleksitas dan keterikatan dalam komputasi dan holografi non-lokal. 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. Pembagian rahasia kuantum untuk struktur akses umum. 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. Batas N besar dari teori medan superkonformal dan supergravitasi. Jurnal internasional fisika teoretis, 38 (4): 1113–1133, 1999. https://doi.org/10.1023/A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] Edward Witten. Ruang anti-de sitter dan holografi. Kemajuan dalam Fisika Teoritis dan Matematika, 2: 253–291, 1998. 10.4310/​ATMP.1998.v2.n2.a2.
https:/​/​doi.org/​10.4310/​ATMP.1998.v2.n2.a2

[19] Daniel Gottsman. Teori berbagi rahasia kuantum. Tinjauan Fisik A, 61 (4): 042311, 2000. https://doi.org/​10.1103/​PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Benjamin Schumacher dan Michael A Nielsen. Pemrosesan data kuantum dan koreksi kesalahan. Tinjauan Fisik A, 54 (4): 2629, 1996. https://​/​doi.org/​10.1103/​PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] Benjamin Schumacher dan Michael D Westmoreland. Perkiraan koreksi kesalahan kuantum. Pemrosesan Informasi Kuantum, 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, and Christoph Meinel. Struktur dan pentingnya kelas logspace-mod. Teori sistem matematika, 25 (3): 223–237, 1992. https://doi.org/10.1007/BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer dan Avi Wigderson. Pada program rentang. Dalam [1993] Prosiding Struktur Tahunan Kedelapan dalam Konferensi Teori Kompleksitas, halaman 102–111. IEEE, 1993/​SCT.10.1109.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien, dan William T Laaser. Masalah baru selesai untuk ruang log nondeterministik. Teori sistem matematika, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt dan Eric Allender. Membuat nondeterminisme tidak ambigu. 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, dan Shiyu Zhou. Isolasi, mencocokkan, dan menghitung batas atas yang seragam dan tidak seragam. 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. Kompleksitas komunikasi. Dalam Kemajuan dalam Komputer, volume 44, halaman 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. Kompleksitas komunikasi gerbang ambang. Combinatorics, Paul Erdos adalah Delapan Puluh, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A Cook. Batas bawah eksponensial untuk program rentang monoton. Pada tahun 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), halaman 406–415. IEEE, 2016/​FOCS.10.1109.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Komputasi Instan Non-Lokal dari Sirkuit Kuantum Kedalaman-T Rendah. Dalam Konferensi ke-11 tentang Teori Komputasi Kuantum, Komunikasi, dan Kriptografi (TQC 2016), volume 61 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 9:1–9:24, Dagstuhl, Jerman, 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

Dikutip oleh

[1] Alex May, “Kerumitan dan keterikatan dalam komputasi dan holografi non-lokal”, Kuantum 6, 864 (2022).

[2] Alex May, Jonathan Sorce, dan Beni Yoshida, "Teorema baji yang terhubung dan konsekuensinya", Jurnal Fisika Energi Tinggi 2022 11, 153 (2022).

[3] Kfir Dolev dan Sam Cree, "Holografi sebagai sumber daya untuk perhitungan kuantum non-lokal", arXiv: 2210.13500, (2022).

[4] Kfir Dolev dan Sam Cree, "Komputasi non-lokal sirkuit kuantum dengan kerucut cahaya kecil", arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, dan Philip Verduyn Lunel, “Menghubungkan komputasi kuantum non-lokal dengan kriptografi teori informasi”, arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs dan Florian Speelman, "Protokol verifikasi posisi kuantum toleran kehilangan qubit tunggal yang aman terhadap penyerang yang terjerat", arXiv: 2212.03674, (2022).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2023-08-10 03:31:42). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2023-08-10 03:31:41).

Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.

Stempel Waktu:

Lebih dari Jurnal Kuantum