Enrutamiento de códigos: un nuevo ataque a la verificación de posición

Reeditado por Platón

seguidores: 0

Enrutamiento de código: un nuevo ataque a la verificación de posición PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Universidad de Stanford

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

La tarea criptográfica de verificación de posición intenta verificar la ubicación de una parte en el espacio-tiempo explotando las limitaciones de la información cuántica y la causalidad relativista. Un esquema de verificación popular conocido como enrutamiento $f$ implica exigir al probador que redirija un sistema cuántico en función del valor de una función booleana $f$. Las estrategias de trampa para el esquema de enrutamiento $f$ requieren que el probador utilice un entrelazamiento previamente compartido, y la seguridad del esquema se basa en suposiciones sobre cuánto entrelazamiento puede manipular un probador. Aquí, damos una nueva estrategia de trampa en la que el sistema cuántico se codifica en un esquema de intercambio de secretos, y la estructura de autorización del esquema de intercambio de secretos se explota para dirigir el sistema de manera apropiada. Esta estrategia completa la tarea de enrutamiento $f$ usando pares EPR $O(SP_p(f))$, donde $SP_p(f)$ es el tamaño mínimo de un programa de extensión sobre el campo $mathbb{Z}_p$ informática $ f$. Esto muestra que podemos atacar eficientemente los esquemas de enrutamiento $f$ siempre que $f$ esté en la clase de complejidad $text{Mod}_ptext{L}$, después de permitir el preprocesamiento local. La mejor construcción anterior logró la clase L, que se cree que está estrictamente dentro de $text{Mod}_ptext{L}$. También mostramos que el tamaño de un esquema de intercambio de secretos cuánticos con función indicadora $f_I$ limita el costo de entrelazamiento de $f$-enrutamiento en la función $f_I$.

► datos BibTeX

@artículo{Cree2023coderoutingnew, doi = {10.22331/q-2023-08-09-1079}, url = {https://doi.org/10.22331/q-2023-08-09-1079}, título = {Código- enrutamiento: un nuevo ataque a la verificación de posición}, autor = {Cree, Joy and May, Alex}, diario = {{Quantum}}, issn = {2521-327X}, editor = {{Verein zur F{“{o} }rderung des Open Access Publizierens in den Quantenwissenschaften}}, volumen = {7}, páginas = {1079}, mes = agosto, año = {2023} }

► referencias

[ 1 ] Nishanth Chandran, Vipul Goyal, Ryan Moriarty y Rafail Ostrovsky. Criptografía basada en posición. En Conferencia Anual Internacional de Criptología, páginas 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 y Timothy P Spiller. Etiquetado cuántico: autenticación de la ubicación mediante información cuántica y restricciones de señalización relativistas. Revisión física A, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[ 3 ] Adrián Kent. Tareas cuánticas en el espacio de Minkowski. Gravedad clásica y cuántica, 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 y Wojciech H Zurek. No se puede clonar un solo cuanto. Naturaleza, 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 y Raymond G Beausoleil. Tagging Systems, 11 de julio de 2006. Patente estadounidense 7,075,438.

[ 6 ] Roberto A Malaney. Comunicaciones dependientes de la ubicación mediante entrelazamiento cuántico. Revisión física 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 y Christian Schaffner. Criptografía cuántica basada en posición: Imposibilidad y construcciones. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/10.1137/130913687.
https: / / doi.org/ 10.1137 / 130913687

[ 8 ] Salman Beigi y Robert König. Computación cuántica instantánea no local simplificada con aplicaciones a la criptografía basada en posición. 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 y Florian Speelman. Un protocolo de verificación de posición de un solo qubit que es seguro contra ataques de múltiples qubits. Física de la naturaleza, páginas 1 a 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 y Florian Speelman. El modelo de manguera de jardín. En Actas de la 4ta conferencia sobre Innovaciones en Informática Teórica, páginas 145–158, 2013. https://doi.org/10.1145/2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[ 11 ] Hartmut Klauck y Supartha Podder. Nuevos límites para el modelo de manguera de jardín. En Fundamentos de la tecnología del software y la informática teórica, 2014. 10.4230/LIPIcs.FSTTCS.2014.481.
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.481

[ 12 ] Srinivasan Arunachalam y Supartha Podder. Recuerdo de comunicación: Complejidad de la comunicación sin memoria. En la 12ª Conferencia sobre Innovaciones en Informática Teórica (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 ] Álex mayo. Tareas cuánticas en holografía. 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 y Jonathan Sorce. La dispersión holográfica requiere una cuña de entrelazamiento conectada. 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 ] Álex May. Complejidad y entrelazamiento en la computación y la holografía no locales. Quantum, 6: 864, noviembre de 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. Intercambio de secretos cuánticos para estructuras de acceso general. 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. El límite de N grande de las teorías de campos superconformes y la supergravedad. Revista internacional de física teórica, 38 (4): 1113–1133, 1999. https://doi.org/10.1023/A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[ 18 ] Eduardo Witten. Espacio anti-de-sitter y holografía. Avances en física teórica y matemática, 2: 253–291, 1998. 10.4310/ATMP.1998.v2.n2.a2.
https://doi.org/10.4310/ATMP.1998.v2.n2.a2

[ 19 ] Daniel Gottesman. Teoría del intercambio de secretos cuánticos. Physical Review A, 61 (4): 042311, 2000. https: / / doi.org/ 10.1103 / PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[ 20 ] Benjamín Schumacher y Michael A. Nielsen. Procesamiento de datos cuánticos y corrección de errores. Revisión física A, 54 (4): 2629, 1996. https://doi.org/10.1103/PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[ 21 ] Benjamín Schumacher y Michael D. Westmoreland. Corrección aproximada de errores cuánticos. Procesamiento de información cuántica, 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 y Christoph Meinel. Estructura e importancia de la clase logspace-mod. Teoría de sistemas matemáticos, 25 (3): 223–237, 1992. https://doi.org/10.1007/BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[ 23 ] Mauricio Karchmer y Avi Wigderson. En los programas de tramo. En [1993] Actas de la Octava Conferencia Anual de Teoría de la Estructura de la Complejidad, páginas 102–111. IEEE, 1993. 10.1109/SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[ 24 ] Neil D Jones, Y Edmund Lien y William T Laaser. Nuevos problemas completos para espacio de registro no determinista. Teoría de sistemas matemáticos, 10 (1): 1–17, 1976. https://doi.org/10.1007/BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[ 25 ] Klaus Reinhardt y Eric Allender. Hacer que el nodeterminismo sea inequívoco. Revista SIAM de Computación, 29 (4): 1118–1131, 2000. https://doi.org/10.1137/S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

[ 26 ] Eric Allender, Klaus Reinhardt y Shiyu Zhou. Aislamiento, comparación y conteo de límites superiores uniformes y no uniformes. Revista de Ciencias de la Computación y Sistemas, 59 (2): 164–181, 1999. https://doi.org/10.1006/jcss.1999.1646.
https: / / doi.org/ 10.1006 / jcss.1999.1646

[ 27 ] Eyal Kushilevitz. Complejidad de la comunicación. En Advances in Computers, volumen 44, páginas 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. La complejidad de la comunicación de las puertas de umbral. Combinatoria, Paul Erdos tiene ochenta, 1: 301–315, 1993.

[ 29 ] Robert Robere, Toniann Pitassi, Benjamin Rossman y Stephen A Cook. Límites inferiores exponenciales para programas de tramos monótonos. En 2016, 57.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS), páginas 406–415. IEEE, 2016. 10.1109/FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[ 30 ] Florián Speelman. Computación instantánea no local de circuitos cuánticos de baja profundidad T. En 11.ª Conferencia sobre teoría de la computación, la comunicación y la criptografía cuánticas (TQC 2016), volumen 61 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 9:1–9:24, Dagstuhl, Alemania, 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

Citado por

[1] Alex May, "Complejidad y entrelazamiento en la computación y la holografía no locales", Cuántica 6, 864 (2022).

[2] Alex May, Jonathan Sorce y Beni Yoshida, “El teorema de la cuña conectada y sus consecuencias”, Revista de física de altas energías 2022 11, 153 (2022).

[3] Kfir Dolev y Sam Cree, “La holografía como recurso para la computación cuántica no local”, arXiv: 2210.13500, (2022).

[4] Kfir Dolev y Sam Cree, “Cómputo no local de circuitos cuánticos con pequeños conos de luz”, arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman y Philip Verduyn Lunel, "Relacionando la computación cuántica no local con la criptografía teórica de la información", arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs y Florian Speelman, “Protocolo de verificación de posición cuántica tolerante a pérdidas de un solo qubit seguro contra atacantes enredados”, arXiv: 2212.03674, (2022).

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2023-08-10 03:31:42). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.

On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2023-08-10 03:31:41).

Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.

Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
PlatoData.Network Vertical Generativo Ai. Empodérate. Accede Aquí.
PlatoAiStream. Inteligencia Web3. Conocimiento amplificado. Accede Aquí.
PlatoESG. Automoción / vehículos eléctricos, Carbón, tecnología limpia, Energía, Ambiente, Solar, Gestión de residuos. Accede Aquí.
Desplazamientos de bloque. Modernización de la propiedad de compensaciones ambientales. Accede Aquí.
Fuente: https://quantum-journal.org/papers/q-2023-08-09-1079/

Sello de tiempo: 9 de agosto de 2023

Sello de tiempo: 21 de marzo, 2024

Reeditado por Platón

Resumen

► datos BibTeX

► referencias

Citado por

TensorCircuit: un marco de software cuántico para la era NISQ

El coste mínimo de comunicación para simular qubits entrelazados

Efectos semienteros frente a enteros en la sincronización cuántica de sistemas de espín

Relaciones cuantitativas entre diferentes contextos de medición

Aceleración de algoritmos cuánticos con precómputo

Solucionador lineal cuántico variacional

Codificación cuántica y análisis de procesos estocásticos de tiempo continuo con aplicaciones financieras

Una cadena de Markov que se mezcla rápidamente a partir de cualquier sistema cuántico de muchos cuerpos con huecos

Un teorema de estructura para modelos ontológicos no contextuales generalizados

Resoluciones espectrales en álgebras de efectos

La catálisis covariante requiere correlaciones y los buenos marcos de referencia cuánticos se degradan poco

Sombras clásicas basadas en mediciones localmente entrelazadas.

Sobre Nosotros

Búsqueda vertical y Ai

Productos

Manténganse Conectados

Mi Cuenta