Tokens cuánticos para firmas digitales

Tokens cuánticos para firmas digitales

Marca de tiempo: 19 de enero de 2023 8:49 a. M.
Nodo de origen: 1908311

Shalev Ben-David1 y O sattath2

1Universidad de Waterloo, Escuela de Ciencias de la Computación David R. Cheriton
2Universidad Ben-Gurion del Negev, Departamento de Ciencias de la Computación

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

Resumen

El pescador atrapó un pez cuántico. “Pescador, déjame ir”, rogó el pez, “y te concederé tres deseos”. El pescador asintió. El pez le dio al pescador una computadora cuántica, tres tokens de firma cuántica y su clave pública clásica. El pez explicó: "para firmar sus tres deseos, use el esquema de firma tokenizado en esta computadora cuántica, luego muestre su firma válida al rey, que me debe un favor".
El pescador usó una de las fichas de firma para firmar el documento "¡Dame un castillo!" y corrió al palacio. El rey ejecutó el clásico algoritmo de verificación usando la clave pública del pez, y dado que era válido, el rey cumplió.
La esposa del pescador quería firmar diez deseos usando las dos fichas de firma que les quedaban. El pescador no quería hacer trampa y navegó en secreto para encontrarse con los peces. “Pez, mi mujer quiere firmar diez deseos más”. Pero el pez no se preocupó: “He aprendido criptografía cuántica siguiendo el cuento anterior (El pescador y su mujer de los hermanos Grimm). Los tokens cuánticos se consumen durante la firma. Tu esposa polinomial no puede ni siquiera firmar cuatro deseos usando las tres fichas de firma que te di”.
"¿Como funciona?" se preguntó el pescador. “¿Has oído hablar del dinero cuántico? Estos son estados cuánticos que se pueden verificar fácilmente pero que son difíciles de copiar. Este esquema de firma cuántica tokenizada amplía el esquema de dinero cuántico de Aaronson y Christiano, por lo que los tokens de firma no se pueden copiar”.
"¿Tiene su esquema propiedades de lujo adicionales?" preguntó el pescador. “Sí, el esquema tiene otras garantías de seguridad: revocabilidad, comprobabilidad y seguridad eterna. Además, si estás en el mar y tu teléfono cuántico solo tiene recepción clásica, puedes usar este esquema para transferir el valor del dinero cuántico a la costa”, dijo el pez, y se alejó nadando.

[Contenido incrustado]

► datos BibTeX

► referencias

[ 1 ] S. Aaronson. Quantum Copy-Protection y Quantum Money. En Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, París, Francia, 15-18 de julio de 2009, páginas 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[ 2 ] Y. Aharonov, J. Anandan y L. Vaidman. Significado de la función de onda. física Rev.A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[ 3 ] S. Aaronson y P. Christiano. Dinero cuántico de subespacios ocultos. En Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, Nueva York, NY, EE. UU., 19 al 22 de mayo de 2012, páginas 41 a 60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[ 4 ] S. Aaronson y P. Christiano. Dinero cuántico de subespacios ocultos. Teoría de la Computación, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[ 5 ] R. Amos, M. Georgiou, A. Kiayias y M. Zhandry. Firmas únicas y aplicaciones para autenticación híbrida cuántica/clásica. En K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath y J. Chuzhoy, editores, Actas del Simposio Anual ACM SIGACT sobre Teoría de la Computación, páginas 255–268. ACM, 2020, Cryptology ePrint Archive: Informe 2020/107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[ 6 ] Y. Aharonov y L. Vaidman. Medida de la onda de Schrödinger de una sola partícula. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[ 7 ] B. Barac. Esperanzas, miedos y ofuscación del software. común ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[ 8 ] CH Bennett, G. Brassard, S. Breidbart y S. Wiesner. Criptografía cuántica, o fichas de metro infalsificables. En Advances in Cryptology, páginas 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[ 9 ] N. Bitansky, Z. Brakerski y YT Kalai. Reducciones post-cuánticas constructivas. En Y. Dodis y T. Shrimpton, editores, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, EE. UU., 15 al 18 de agosto de 2022, Actas, Parte III, volumen 13509 de Conferencia Notes in Computer Science, páginas 654–683. Primavera, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[ 10 ] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, YT Kalai, O. Paneth y A. Rosen. La imposibilidad de ofuscación con entrada auxiliar o un simulador universal. En JA Garay y R. Gennaro, editores, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, EE. UU., 17-21 de agosto de 2014, Actas, Parte II, volumen 8617 de Lecture Notes in Computer Science, páginas 71–89. Springer, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[ 11 ] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, SP Vadhan y K. Yang. Sobre la (im)posibilidad de ofuscar programas. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[ 12 ] H. Bombín. Puertas de Clifford por deformación de código. Nueva Revista de Física, 13(4):043005, 2011.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​4/​043005
http:/​/​stacks.iop.org/​1367-2630/​13/​i=4/​a=043005

[ 13 ] G. Brassard. Búsqueda en una guía telefónica de Quantum. Ciencia, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[ 14 ] A. Behera, O. Sattath y U. Shinar. Tokens cuánticos tolerantes al ruido para MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[ 15 ] D. Boneh y M. Zhandry. Códigos de autenticación de mensajes Quantum-Secure. En T. Johansson y PQ Nguyen, editores, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Atenas, Grecia, 26-30 de mayo de 2013. Actas, volumen 7881 de Lecture Notes in Computer Ciencia, páginas 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[ 16 ] R. Cleve y D. Gottesman. Cálculos eficientes de codificaciones para la corrección de errores cuánticos. física Rev. A, 56:76–82, julio de 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[ 17 ] K. Chung, M. Georgiou, C. Lai y V. Zikas. Criptografía con puertas traseras desechables. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Informe 2018/352.
https: / / doi.org/ 10.3390 / cryptography3030022

[ 18 ] P. Cristiano. Comunicación personal, 2015.

[ 19 ] A. Coladangelo, J. Liu, Q. Liu y M. Zhandry. Conjuntos ocultos y aplicaciones para la criptografía no clonable, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[ 20 ] S. Chakraborty, J. Radhakrishnan y N. Raghunathan. Límites para la reducción de errores con pocas consultas cuánticas. En Aproximación, Aleatorización y Optimización Combinatoria, Algoritmos y Técnicas, 8º Taller Internacional sobre Algoritmos de Aproximación para Problemas de Optimización Combinatoria, APROX. 2005 y RANDOM 2005, Berkeley, CA, EE. UU., 22-24 de agosto de 2005, Actas, páginas 245–256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[ 21 ] R. Canetti, GN Rothblum y M. Varia. Ofuscación de la Membresía Hiperplano. En D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zúrich, Suiza, 9 al 11 de febrero de 2010. Actas, volumen 5978 de Lecture Notes in Computer Science, páginas 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[ 22 ] W. Diffie y ME Hellman. Nuevas direcciones en criptografía. Trans. IEEE. Teoría de la información, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[ 23 ] YZ Ding y MO Rabin. Hipercifrado y seguridad eterna. En H. Alt y A. Ferreira, editores, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, France, March 14-16, 2002, Proceedings, volumen 2285 de Lecture Notes in Computer Science, páginas 1–26. Springer, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[ 24 ] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj y P. Shor. Restauración de estado cuántico y tomografía de copia única para estados fundamentales de hamiltonianos. física Rev. Lett., 105:190503, noviembre de 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[ 25 ] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski y P. Shor. Dinero cuántico de nudos. En Actas de la 3.ª Conferencia sobre Innovaciones en Informática Teórica, páginas 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[ 26 ] D. Gavinsky. Dinero cuántico con verificación clásica. En IEEE 27th Annual Conference on Computational Complexity, páginas 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[ 27 ] S. Goldwasser y YT Kalai. Sobre la imposibilidad de ofuscación con entrada auxiliar. En 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 ​​de octubre de 2005, Pittsburgh, PA, EE. UU., Actas, páginas 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[ 28 ] M. Georgiou e I. Kerenidis. Nuevas Construcciones por Dinero Cuántico. En S. Beigi y R. König, editores, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20-22 de mayo de 2015, Bruselas, Bélgica, volumen 44 de LIPIcs, páginas 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[ 29 ] O. Goldreich. Los fundamentos de la criptografía - Vol. 2, aplicaciones básicas. Prensa de la Universidad de Cambridge, 2004.

[ 30 ] M. Grassl, M. Rötteler y T. Beth. Circuitos cuánticos eficientes para códigos de corrección de errores cuánticos no Qubit. En t. J. Encontrado. computar Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[ 31 ] J. Katz e Y. Lindell. Introducción a la criptografía moderna, segunda edición. CRC Press, 2014.

[ 32 ] NA Lynch. Algoritmos Distribuidos. Morgan Kaufmann, 1996.

[ 33 ] M. Mosca y D. Stebila. Monedas cuánticas, volumen 523 de Contemp. Matemáticas, páginas 35–47. Amer. Matemáticas. Soc., 2010.

[ 34 ] MC Pena, RD Díaz, J. Faugère, LH Encinas, and L. Perret. Criptoanálisis no cuántico de la versión ruidosa del esquema de dinero cuántico de Aaronson-Christiano. Seguridad de la información del IET, 13(4):362–366, 2019.
https:/​/​doi.org/​10.1049/​iet-ifs.2018.5307

[ 35 ] MC Peña, J. Faugère y L. Perret. Criptoanálisis algebraico de un esquema de dinero cuántico El caso libre de ruido. En J. Katz, editor, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, EE. UU., 30 de marzo – 1 de abril de 2015, Actas, volumen 9020 de Lecture Notes en Ciencias de la Computación, páginas 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[ 36 ] A. Prasad. Contar subespacios de un espacio vectorial finito — 1. Resonance, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[ 37 ] F. Pastawski, NY Yao, L. Jiang, MD Lukin y JI Cirac. Fichas cuánticas tolerantes al ruido infalsificables. Actas de la Academia Nacional de Ciencias, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[ 38 ] R. Radian y O. Sattath. Dinero semicuántico. En Actas de la 1.ª Conferencia ACM sobre avances en tecnologías financieras, AFT 2019, Zúrich, Suiza, 21 y 23 de octubre de 2019, páginas 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[ 39 ] R. Radian y O. Sattath. Dinero semicuántico. Journal of Cryptology, 35(2), enero de 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[ 40 ] O. Sattath. Contratos Quantum Prudent con aplicaciones a Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[ 41 ] O. Sattath. Criptografía no clonable, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[ 42 ] O. Shmueli. Dinero cuántico de clave pública con un banco clásico. En S. Leonardi y A. Gupta, editores, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Roma, Italia, 20 al 24 de junio de 2022, páginas 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[ 43 ] O. Shmueli. Firmas tokenizadas semicuánticas. En Y. Dodis y T. Shrimpton, editores, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, EE. UU., 15-18 de agosto de 2022, Actas, Parte I, volumen 13507 de Conferencia Notes in Computer Science, páginas 296–319. Primavera, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[ 44 ] T. Tulsi, LK Grover y A. Patel. Un nuevo algoritmo para la búsqueda cuántica de punto fijo. Información y computación cuánticas, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[ 45 ] Y. Tokunaga, T. Okamoto y N. Imoto. Efectivo cuántico anónimo. En ERATO Conference on Quantum Information Science, 2003.

[ 46 ] D. Unruh. Cifrado de liberación temporizada cuántica revocable. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[ 47 ] D. Unruh. Cómputo multipartidista eterno. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[ 48 ] S. Wiesner. Codificación conjugada. ACM Sigact News, 15 (1): 78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[ 49 ] WK Wootters y WH Zurek. Un solo cuanto no puede ser clonado. Naturaleza, 299(5886):802–803, 1982.

[ 50 ] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell y MJ Sellars. Espines nucleares direccionables ópticamente en un sólido con un tiempo de coherencia de seis horas. Nature, 517(7533):177–180, enero de 2015.
https: / / doi.org/ 10.1038 / nature14025

[ 51 ] M. Zhandry. El rayo cuántico nunca golpea el mismo estado dos veces, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[ 52 ] M. Zhandry. Los rayos cuánticos nunca golpean el mismo estado dos veces. O: Dinero Cuántico a partir de Supuestos Criptográficos. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Citado por

[1] S. Pirandola, UL Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, JL Pereira, M. Razavi, J Shamsul Shaari, M. Tomamichel, VC Usenko, G. Vallone, P. Villoresi y P. Wallden, “Avances en criptografía cuántica”, Avances en Óptica y Fotónica 12 4, 1012 (2020).

[2] Douglas Scott, "Parodias científicas, bromas de física y travesuras astronómicas", arXiv: 2103.17057.

[3] Thomas Vidick y Tina Zhang, "Pruebas clásicas del conocimiento cuántico", arXiv: 2005.01691.

[4] O Sattath, “Contratos prudentes cuánticos con aplicaciones a Bitcoin”, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry y Ruizhe Zhang, “Nuevos enfoques para la protección anticopia cuántica”, arXiv: 2004.09674.

[6] Roy Radian y Or Sattath, “Dinero semicuántico”, arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser y Umesh Vazirani, “Cifrado negable en un mundo cuántico”, arXiv: 2112.14988.

[8] Prabhanjan Ananth y Rolando L. La Placa, “Arrendamiento de software seguro”, arXiv: 2005.05289.

[9] O Sattath y Shai Wyborski, “Uncloneable Decryptors from Quantum Copy-Protection”, arXiv: 2203.05866.

[10] Andrea Coladangelo y Or Sattath, “Una solución de dinero cuántico al problema de escalabilidad de la cadena de bloques”, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery y Mark Zhandry, "Otra ronda de romper y hacer dinero cuántico: cómo no construirlo a partir de celosías y más", arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu y Mark Zhandry, "Cosets ocultos y aplicaciones a la criptografía no clonable", arXiv: 2107.05692.

[13] O Sattath, “Criptografía no clonable”, arXiv: 2210.14265.

[14] Amit Behera y Or Sattath, “Monedas cuánticas casi públicas”, arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian y Hong-Sheng Zhou, “Hacia memorias únicas cuánticas de hardware sin estado”, arXiv: 1810.05226.

[16] Niraj Kumar, “Dinero cuántico robusto prácticamente factible con verificación clásica”, arXiv: 1908.04114.

[17] O Sattath y Uriel Shinar, “Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism”, arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski y Yael Tauman Kalai, “Reducciones poscuánticas constructivas”, arXiv: 2203.02314.

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2023-01-20 14:01:05). 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-01-20 14:01:00).

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.

Sello de tiempo:

Mas de Diario cuántico