Δρομολόγηση κώδικα: μια νέα επίθεση στην επαλήθευση θέσης

Δρομολόγηση κώδικα: μια νέα επίθεση στην επαλήθευση θέσης

Χρονική σήμανση: 9 Αυγούστου 2023 11:18 π.μ.
Δρομολόγηση κώδικα: μια νέα επίθεση στην επαλήθευση θέσης PlatoBlockchain Data Intelligence. Κάθετη αναζήτηση. Ολα συμπεριλαμβάνονται.

Joy Cree και Άλεξ Μέι

Πανεπιστήμιο του Στάνφορντ

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Η κρυπτογραφική εργασία της επαλήθευσης θέσης επιχειρεί να επαληθεύσει τη θέση ενός μέρους στον χωροχρόνο εκμεταλλευόμενοι περιορισμούς στην κβαντική πληροφορία και τη σχετικιστική αιτιότητα. Ένα δημοφιλές σχήμα επαλήθευσης γνωστό ως $f$-routing περιλαμβάνει την απαίτηση από τον prover να ανακατευθύνει ένα κβαντικό σύστημα με βάση την τιμή μιας Boolean συνάρτησης $f$. Οι στρατηγικές εξαπάτησης για το σχήμα δρομολόγησης $f$ απαιτούν από τον prover να χρησιμοποιεί προ-κοινή εμπλοκή και η ασφάλεια του συστήματος βασίζεται σε υποθέσεις σχετικά με το πόση εμπλοκή μπορεί να χειριστεί ένας prover. Εδώ, δίνουμε μια νέα στρατηγική εξαπάτησης στην οποία το κβαντικό σύστημα κωδικοποιείται σε ένα σχήμα κοινής χρήσης μυστικών και η δομή εξουσιοδότησης του συστήματος κοινής χρήσης μυστικών αξιοποιείται για να κατευθύνει το σύστημα κατάλληλα. Αυτή η στρατηγική ολοκληρώνει την εργασία $f$-routing χρησιμοποιώντας ζεύγη $O(SP_p(f))$ EPR, όπου η $SP_p(f)$ είναι το ελάχιστο μέγεθος ενός προγράμματος span στο πεδίο $mathbb{Z}_p$ computing $ f$. Αυτό δείχνει ότι μπορούμε να επιτεθούμε αποτελεσματικά σε σχήματα δρομολόγησης $f$ όποτε το $f$ βρίσκεται στην κατηγορία πολυπλοκότητας $text{Mod}_ptext{L}$, αφού επιτραπεί η τοπική προεπεξεργασία. Η καλύτερη προηγούμενη κατασκευή πέτυχε την κατηγορία L, η οποία πιστεύεται ότι είναι αυστηρά εντός του $text{Mod}_ptext{L}$. Δείχνουμε επίσης ότι το μέγεθος ενός σχήματος κοινής χρήσης κβαντικών μυστικών με συνάρτηση δείκτη $f_I$ άνω ορίων κοστίζει το κόστος εμπλοκής $f$-δρομολόγησης στη συνάρτηση $f_I$.

► Δεδομένα BibTeX

► Αναφορές

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty και Rafail Ostrovsky. Κρυπτογραφία βάσει θέσης. Στο Ετήσιο Διεθνές Συνέδριο Κρυπτολογίας, σελίδες 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 και Timothy P Spiller. Κβαντική σήμανση: Έλεγχος ταυτότητας τοποθεσίας μέσω κβαντικών πληροφοριών και σχετικιστικών περιορισμών σηματοδότησης. Physical Review A, 84 (1): 012326, 2011. https://doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Άντριαν Κεντ. Κβαντικές εργασίες στον χώρο Minkowski. 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 και Wojciech H Zurek. Ένα μόνο κβάντο δεν μπορεί να κλωνοποιηθεί. 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 και Raymond G Beausoleil. Συστήματα ετικετών, 11 Ιουλίου 2006. Ευρεσιτεχνία ΗΠΑ 7,075,438.

[6] Robert A Malaney. Επικοινωνίες που εξαρτώνται από τη θέση χρησιμοποιώντας κβαντική εμπλοκή. 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 και Christian Schaffner. Κβαντική κρυπτογραφία με βάση τη θέση: Αδυναμία και κατασκευές. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi και Robert König. Απλοποιημένος στιγμιαίος μη τοπικός κβαντικός υπολογισμός με εφαρμογές κρυπτογραφίας με βάση τη θέση. 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 και Florian Speelman. Ένα πρωτόκολλο επαλήθευσης θέσης ενός qubit που είναι ασφαλές έναντι επιθέσεων πολλαπλών qubit. Nature Physics, σελίδες 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 και Florian Speelman. Το μοντέλο λάστιχου κήπου. Στα Πρακτικά του 4ου συνεδρίου για τις Καινοτομίες στη Θεωρητική Επιστήμη των Υπολογιστών, σελίδες 145–158, 2013. https://doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck και Supartha Podder. Νέα όρια για το μοντέλο λάστιχου κήπου. 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 και Supartha Podder. Αναμνηστικό επικοινωνίας: Πολυπλοκότητα επικοινωνίας χωρίς μνήμη. Στο 12ο Συνέδριο Innovations in Theoretical Computer Science (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] Άλεξ Μέι. Κβαντικές εργασίες στην ολογραφία. 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 και Jonathan Sorce. Η ολογραφική σκέδαση απαιτεί μια συνδεδεμένη σφήνα εμπλοκής. 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] Άλεξ Μέι. Πολυπλοκότητα και εμπλοκή σε μη τοπικούς υπολογισμούς και ολογραφία. Quantum, 6: 864, Νοέμβριος 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. Κβαντική κοινή χρήση μυστικών για δομές γενικής πρόσβασης. arXiv προεκτύπωση 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] Χουάν Μαλντασένα. Το όριο μεγάλου-Ν των υπερσυμμορφικών θεωριών πεδίου και της υπερβαρύτητας. International journal of theoretical physics, 38 (4): 1113–1133, 1999. https://​/​doi.org/​10.1023/​A:1026654312961.
https: / / doi.org/ 10.1023 / Α: 1026654312961

[18] Έντουαρντ Βίτεν. Anti-de sitter χώρος και ολογραφία. 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] Ντάνιελ Γκότσεμαν. Θεωρία της κβαντικής μυστικής ανταλλαγής. 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 και Michael A Nielsen. Κβαντική επεξεργασία δεδομένων και διόρθωση σφαλμάτων. 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 και Michael D Westmoreland. Κατά προσέγγιση κβαντική διόρθωση σφαλμάτων. Quantum Information Processing, 1 (1): 5–12, 2002. https://doi.org/​10.1023/​A:1019653202562.
https: / / doi.org/ 10.1023 / Α: 1019653202562

[22] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf και Christoph Meinel. Δομή και σημασία της κλάσης logspace-mod. Mathematical systems theory, 25 (3): 223–237, 1992. https://doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer και Avi Wigderson. Σε προγράμματα span. Στο [1993] Proceedings of the Egth Annual Structure in Complexity Theory Conference, σελίδες 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https://doi.org/​10.1109/​SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien και William T Laaser. Νέα προβλήματα ολοκληρώθηκαν για μη ντετερμινιστικό χώρο καταγραφής. Mathematical systems theory, 10 (1): 1–17, 1976. https://doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt και Eric Allender. Κάνοντας τον μη ντετερμινισμό ξεκάθαρο. 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 και Shiyu Zhou. Απομόνωση, αντιστοίχιση και μέτρηση ομοιόμορφων και ανομοιόμορφων άνω ορίων. 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. Πολυπλοκότητα επικοινωνίας. Στο Advances in Computers, τόμος 44, σελίδες 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] Νόαμ Νισάν. Η πολυπλοκότητα επικοινωνίας των πυλών κατωφλίου. Combinatorics, Paul Erdos is Eighty, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman και Stephen A Cook. Εκθετικά κάτω όρια για προγράμματα μονοτονικού εύρους. Το 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), σελίδες 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Φλόριαν Σπίλμαν. Στιγμιαίος μη τοπικός υπολογισμός κβαντικών κυκλωμάτων χαμηλού βάθους Τ. Στο 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), τόμος 61 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 9:1–9:24, Dagstuhl, Γερμανία, 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

Αναφέρεται από

[1] Alex May, «Πολυπλοκότητα και εμπλοκή σε μη τοπικούς υπολογισμούς και ολογραφία», Κβαντικό 6, 864 (2022).

[2] Alex May, Jonathan Sorce και Beni Yoshida, «Το θεώρημα της συνδεδεμένης σφήνας και οι συνέπειές του», Journal of High Energy Physics 2022 11, 153 (2022).

[3] Kfir Dolev και Sam Cree, «Holography as a resource for non-local quantum computation». arXiv: 2210.13500, (2022).

[4] Kfir Dolev και Sam Cree, «Μη τοπικός υπολογισμός κβαντικών κυκλωμάτων με μικρούς κώνους φωτός», arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman και Philip Verduyn Lunel, «Σχέση του μη τοπικού κβαντικού υπολογισμού με τη θεωρητική κρυπτογραφία πληροφοριών». arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs και Florian Speelman, «Πρωτόκολλο επαλήθευσης κβαντικής θέσης με ανεκτικό απώλειας ενός qubit ασφαλές έναντι εμπλεκόμενων εισβολέων», arXiv: 2212.03674, (2022).

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2023-08-10 03:31:42). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2023-08-10 03:31:41).

Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal