Routage de code : une nouvelle attaque contre la vérification de position

Republié par Platon

Suiveurs: 0

Code-routage : une nouvelle attaque sur la vérification de position PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

L'Université de Stanford

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

La tâche cryptographique de vérification de position tente de vérifier la localisation d'une partie dans l'espace-temps en exploitant les contraintes sur l'information quantique et la causalité relativiste. Un système de vérification populaire connu sous le nom de routage $f$ implique d'exiger du prouveur qu'il redirige un système quantique en fonction de la valeur d'une fonction booléenne $f$. Les stratégies de triche pour le schéma de routage $f$ nécessitent que le prouveur utilise une intrication pré-partagée, et la sécurité du schéma repose sur des hypothèses sur le degré d'intrication qu'un prouveur peut manipuler. Ici, nous donnons une nouvelle stratégie de triche dans laquelle le système quantique est codé dans un schéma de partage de secrets, et la structure d'autorisation du schéma de partage de secrets est exploitée pour diriger le système de manière appropriée. Cette stratégie termine la tâche de routage $f$ en utilisant des paires $O(SP_p(f))$ EPR, où $SP_p(f)$ est la taille minimale d'un programme span sur le champ $mathbb{Z}_p$ computing $ f$. Cela montre que nous pouvons attaquer efficacement les schémas de routage $f$ chaque fois que $f$ est dans la classe de complexité $text{Mod}_ptext{L}$, après avoir autorisé le prétraitement local. La meilleure construction antérieure atteignait la classe L, qui est censée être strictement à l'intérieur de $text{Mod}_ptext{L}$. Nous montrons également que la taille d'un schéma de partage de secret quantique avec la fonction indicatrice $f_I$ limite le coût d'intrication du routage $f$ sur la fonction $f_I$.

► Données BibTeX

@article{Cree2023coderoutingnew, doi = {10.22331/q-2023-08-09-1079}, url = {https://doi.org/10.22331/q-2023-08-09-1079}, titre = {Code- routage : une nouvelle attaque contre la vérification de position}, auteur = {Cree, Joy and May, Alex}, journal = {{Quantum}}, issn = {2521-327X}, éditeur = {{Verein zur F{“{o} }rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1079}, mois = août, année = {2023} }

► Références

Nishanth Chandran, Vipul Goyal, Ryan Moriarty et Rafail Ostrovsky. Cryptographie basée sur la position. Dans Conférence internationale annuelle de cryptologie, pages 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

Adrian Kent, William J Munro et Timothy P Spiller. Marquage quantique : authentification de la localisation via des informations quantiques et des contraintes de signalisation relativistes. Examen physique A, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

Adrien Kent. Tâches quantiques dans l'espace de Minkowski. Gravité classique et quantique, 29 (22) : 224013, 2012. 10.1088/0264-9381/29/22/224013.
https://doi.org/10.1088/0264-9381/29/22/224013

William K Wootters et Wojciech H Zurek. Un seul quantum ne peut pas être cloné. Nature, 299 (5886) : 802-803, 1982. https://doi.org/10.1038/299802a0.
https: / / doi.org/ 10.1038 / 299802a0

Adrian P Kent, William J Munro, Timothy P Spiller et Raymond G Beausoleil. Systèmes d'étiquetage, 11 juillet 2006. Brevet américain 7,075,438.

Robert A Malaney. Communications géodépendantes utilisant l'intrication quantique. Examen physique A, 81 (4) : 042319, 2010. https://doi.org/10.1103/PhysRevA.81.042319.
https: / / doi.org/ 10.1103 / PhysRevA.81.042319

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky et Christian Schaffner. Cryptographie quantique basée sur la position : impossibilité et constructions. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/10.1137/130913687.
https: / / doi.org/ 10.1137 / 130913687

Salman Beigi et Robert König. Calcul quantique non local instantané simplifié avec des applications à la cryptographie basée sur la position. 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

Andreas Bluhm, Matthias Christandl et Florian Speelman. Un protocole de vérification de position sur un seul qubit sécurisé contre les attaques multi-qubits. Physique de la nature, pages 1 à 4, 2022. https://doi.org/10.1038/s41567-022-01577-0.
https://doi.org/10.1038/s41567-022-01577-0

Harry Buhrman, Serge Fehr, Christian Schaffner et Florian Speelman. Le modèle du tuyau d'arrosage. Dans Actes de la 4e conférence sur les innovations en informatique théorique, pages 145–158, 2013. https://doi.org/10.1145/2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

Hartmut Klauck et Supartha Podder. De nouvelles limites pour le modèle de tuyau d'arrosage. Dans Fondements de la technologie logicielle et de l'informatique théorique, 2014. 10.4230/LIPIcs.FSTTCS.2014.481.
https://doi.org/10.4230/LIPics.FSTTCS.2014.481

Srinivasan Arunachalam et Supartha Podder. Souvenir de communication : complexité de la communication sans mémoire. Lors de la 12e conférence sur les innovations en informatique théorique (ITCS 2021). Château Dagstuhl-Leibniz-Zentrum für Informatik, 2021. 10.4230/LIPIcs.ITCS.2021.61.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.61

Alex May. Tâches quantiques en holographie. 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

Alex May, Geoff Penington et Jonathan Sorce. La diffusion holographique nécessite un coin d'intrication connecté. 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

Alex May. Complexité et intrication dans le calcul non local et l'holographie. Quantique, 6 : 864, novembre 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

Adam D Smith. Partage de secret quantique pour les structures d'accès générales. 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

Juan Maldacena. La limite du grand N des théories des champs superconformes et de la supergravité. Journal international de physique théorique, 38 (4): 1113–1133, 1999. https://doi.org/10.1023/A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

Édouard Witten. Espace anti-de-sitter et holographie. Avancées en physique théorique et mathématique, 2 : 253–291, 1998. 10.4310/ATMP.1998.v2.n2.a2.
https://doi.org/10.4310/ATMP.1998.v2.n2.a2

Daniel Gottesman. Théorie du partage de secrets quantiques. Physical Review A, 61 (4): 042311, 2000. https: / / doi.org/ 10.1103 / PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

Benjamin Schumacher et Michael A. Nielsen. Traitement des données quantiques et correction d'erreurs. Examen physique A, 54 (4) : 2629, 1996. https://doi.org/10.1103/PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

Benjamin Schumacher et Michael D. Westmoreland. Correction d'erreur quantique approximative. Traitement de l'information quantique, 1 (1) : 5–12, 2002. https://doi.org/10.1023/A:1019653202562.
https: / / doi.org/ 10.1023 / A: 1019653202562

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf et Christoph Meinel. Structure et importance de la classe logspace-mod. Théorie des systèmes mathématiques, 25 (3) : 223-237, 1992. https://doi.org/10.1007/BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

Mauricio Karchmer et Avi Wigderson. Sur les programmes d'envergure. Dans [1993] Actes de la huitième conférence annuelle sur la structure de la théorie de la complexité, pages 102–111. IEEE, 1993. 10.1109/SCT.1993.336536.
https:///doi.org/10.1109/SCT.1993.336536

Neil D Jones, Y Edmund Lien et William T Laaser. Nouveaux problèmes terminés pour l'espace de journalisation non déterministe. Théorie des systèmes mathématiques, 10 (1) : 1–17, 1976. https://doi.org/10.1007/BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

Klaus Reinhardt et Eric Allender. Rendre le non-déterminisme sans ambiguïté. SIAM Journal on Computing, 29 (4) : 1118-1131, 2000. https://doi.org/10.1137/S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

Eric Allender, Klaus Reinhardt et Shiyu Zhou. Isolement, correspondance et comptage des limites supérieures uniformes et non uniformes. 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

Eyal Kushilevitz. Complexité des communications. Dans Advances in Computers, volume 44, pages 331 à 360. Elsevier, 1997. https://doi.org/10.1016/S0065-2458(08)60342-3.
https://doi.org/10.1016/S0065-2458(08)60342-3

Noam Nisan. La complexité de communication des portes à seuil. Combinatoire, Paul Erdos a quatre-vingts ans, 1 : 301-315, 1993.

Robert Robere, Toniann Pitassi, Benjamin Rossman et Stephen A Cook. Limites inférieures exponentielles pour les programmes de portée monotones. En 2016, 57e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), pages 406 à 415. IEEE, 2016. 10.1109/FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

Florian Speelman. Calcul instantané non local de circuits quantiques à faible profondeur de T. Dans 11e Conférence sur la théorie du calcul quantique, de la communication et de la cryptographie (TQC 2016), volume 61 de Leibniz International Proceedings in Informatics (LIPIcs), pages 9 :1–9 :24, Dagstuhl, Allemagne, 2016. Schloss Dagstuhl–Leibniz- Centre d'informatique. ISBN978-3-95977-019-4. 10.4230/LIPIcs.TQC.2016.9.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2016.9

Cité par

[1] Alex May, « Complexité et intrication dans le calcul non local et l'holographie », Quantique 6, 864 (2022).

[2] Alex May, Jonathan Sorce et Beni Yoshida, "Le théorème du coin connexe et ses conséquences", Journal de physique des hautes énergies 2022 11, 153 (2022).

[3] Kfir Dolev et Sam Cree, "L'holographie comme ressource pour le calcul quantique non local", arXiv: 2210.13500, (2022).

[4] Kfir Dolev et Sam Cree, "Calcul non local de circuits quantiques avec de petits cônes de lumière", arXiv: 2203.10106, (2022).

[5] René Allerstorfer, Harry Buhrman, Alex May, Florian Speelman et Philip Verduyn Lunel, « Relier le calcul quantique non local à la cryptographie théorique de l'information », arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs et Florian Speelman, « Protocole de vérification de position quantique tolérant aux pertes sur un seul qubit sécurisé contre les attaquants intriqués », arXiv: 2212.03674, (2022).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-08-10 03:31:42). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2023-08-10 03:31:41).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
PlatoData.Network Ai générative verticale. Autonomisez-vous. Accéder ici.
PlatoAiStream. Intelligence Web3. Connaissance Amplifiée. Accéder ici.
PlatonESG. Automobile / VE, Carbone, Technologie propre, Énergie, Environnement, Solaire, La gestion des déchets. Accéder ici.
Décalages de bloc. Modernisation de la propriété des compensations environnementales. Accéder ici.
La source: https://quantum-journal.org/papers/q-2023-08-09-1079/

Horodatage: 9 août 2023

Horodatage: 21 Mar 2024

Republié par Platon

Abstract

► Données BibTeX

► Références

Cité par

TensorCircuit : un cadre logiciel quantique pour l'ère NISQ

Le coût de communication minimal pour simuler des qubits intriqués

Effets demi-entier vs entier dans la synchronisation quantique des systèmes de spin

Relations quantitatives entre différents contextes de mesure

Accélérer les algorithmes quantiques avec le précalcul

Solveur linéaire quantique variationnel

Codage et analyse quantiques sur un processus stochastique en temps continu avec des applications financières

Une chaîne de Markov à mélange rapide à partir de n'importe quel système quantique à N corps espacé

Un théorème de structure pour les modèles ontologiques généralisés non contextuels

Résolutions spectrales dans les algèbres d'effet

La catalyse covariante nécessite des corrélations et de bons cadres de référence quantiques se dégradent peu

Ombres classiques basées sur des mesures localement intriquées

À propos de nous

Recherche verticale et Ai

Plateforme

Restez à l'affût

Compte