Tokens quânticos para assinaturas digitais

Tokens quânticos para assinaturas digitais

Carimbo de data / hora: 19 de janeiro de 2023 8h49

Shalev Ben-David1 e Ou Sattath2

1Universidade de Waterloo, Escola de Ciência da Computação David R. Cheriton
2Universidade Ben-Gurion do Negev, Departamento de Ciência da Computação

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

O pescador pegou um peixe quântico. “Pescador, por favor, deixe-me ir”, implorou o peixe, “e eu lhe concederei três desejos”. O pescador concordou. O peixe deu ao pescador um computador quântico, três tokens de assinatura quântica e sua chave pública clássica. O peixe explicou: “para assinar seus três desejos, use o esquema de assinatura tokenizada deste computador quântico e depois mostre sua assinatura válida ao rei, que me deve um favor”.
O pescador usou uma das fichas para assinar o documento “dê-me um castelo!” e correu para o palácio. O rei executou o algoritmo de verificação clássico usando a chave pública do peixe e, como era válido, o rei obedeceu.
A esposa do pescador queria assinar dez desejos usando as duas fichas de assinatura restantes. O pescador não quis trapacear e navegou secretamente ao encontro dos peixes. “Peixe, minha esposa quer assinar mais dez desejos”. Mas o peixe não se preocupou: “Aprendi criptografia quântica seguindo a história anterior (O Pescador e Sua Mulher, dos irmãos Grimm). Os tokens quânticos são consumidos durante a assinatura. Sua esposa polinomial não consegue nem assinar quatro desejos usando as três fichas de assinatura que eu lhe dei”.
"Como funciona?" perguntou o pescador. “Você já ouviu falar de dinheiro quântico? Estes são estados quânticos que podem ser facilmente verificados, mas são difíceis de copiar. Este esquema de assinatura quântica tokenizada estende o esquema de dinheiro quântico de Aaronson e Christiano, e é por isso que os tokens de assinatura não podem ser copiados”.
“Seu esquema tem propriedades sofisticadas adicionais?” perguntou o pescador. “Sim, o esquema tem outras garantias de segurança: revogabilidade, testabilidade e segurança eterna. Além disso, se você estiver no mar e seu telefone quântico tiver apenas recepção clássica, você poderá usar esse esquema para transferir o valor do dinheiro quântico para a costa”, disse o peixe, e nadou para longe.

Tokens quânticos para assinaturas digitais PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

[Conteúdo incorporado]

► dados BibTeX

► Referências

[1] S. Aaronson. Proteção contra cópia quântica e dinheiro quântico. Em Anais da 24ª Conferência Anual IEEE sobre Complexidade Computacional, CCC 2009, Paris, França, 15-18 de julho de 2009, páginas 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan e L. Vaidman. Significado da função de onda. Física. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson e P. Christiano. Dinheiro quântico de subespaços ocultos. Em Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, EUA, 19 a 22 de maio de 2012, páginas 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson e P. Christiano. Dinheiro Quântico de Subespaços Ocultos. Teoria da Computação, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias e M. Zhandry. Assinaturas e aplicações únicas para autenticação híbrida quântica/clássica. Em K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath e J. Chuzhoy, editores, Procedings of the Annual ACM SIGACT Symposium on Theory of Computing, páginas 255–268. ACM, 2020, Arquivo ePrint de criptologia: Relatório 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov e L. Vaidman. Medição da onda de Schrödinger de uma única partícula. Cartas de Física A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Baraque. Esperanças, medos e ofuscação de software. Comum. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart e S. Wiesner. Criptografia quântica ou tokens de metrô não falsificáveis. Em Avanços na Criptologia, páginas 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski e YT Kalai. Reduções pós-quânticas construtivas. Em Y. Dodis e T. Shrimpton, editores, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Bárbara, CA, EUA, 15 a 18 de agosto de 2022, Proceedings, Parte III, volume 13509 da Palestra Notas em Ciência da Computação, 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 e A. Rosen. A impossibilidade de ofuscação com entrada auxiliar ou simulador universal. Em JA Garay e R. Gennaro, editores, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Bárbara, CA, EUA, 17 a 21 de agosto de 2014, Proceedings, Part II, volume 8617 of 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 e K. Yang. Sobre a (im)possibilidade de ofuscar programas. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Portas de Clifford por deformação de código. Novo Jornal 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. Pesquisando uma lista telefônica quântica. Ciência, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath e U. Shinar. Tokens quânticos tolerantes a ruído para MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh e M. Zhandry. Códigos de autenticação de mensagens Quantum-Secure. Em T. Johansson e PQ Nguyen, editores, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Atenas, Grécia, 26 a 30 de maio de 2013. Anais, volume 7881 de Lecture Notes in Computer Ciência, páginas 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve e D. Gottesman. Cálculos eficientes de codificações para correção quântica de erros. Física. Rev. A, 56:76–82, julho de 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai e V. Zikas. Criptografia com backdoors descartáveis. Cryptogr., 3(3):22, 2019, Arquivo Cryptology ePrint: Relatório 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P. Cristiano. Comunicação pessoal, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu e M. Zhandry. Cosets ocultos e aplicativos para criptografia não clonável, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan e N. Raghunathan. Limites para redução de erros com poucas consultas quânticas. Em Aproximação, Randomização e Otimização Combinatória, Algoritmos e Técnicas, 8º Workshop Internacional sobre Algoritmos de Aproximação para Problemas de Otimização Combinatória, APPROX 2005 e RANDOM 2005, Berkeley, CA, EUA, 22 a 24 de agosto de 2005, Proceedings, páginas 245–256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum e M. Varia. Ofuscação de membros do hiperplano. Em D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurique, Suíça, 9 a 11 de fevereiro de 2010. Proceedings, volume 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 e ME Hellman. Novos rumos em criptografia. IEEE Trans. Teoria da Informação, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding e MO Rabin. Hipercriptografia e segurança eterna. Em H. Alt e A. Ferreira, editores, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, França, 14 a 16 de março de 2002, Proceedings, volume 2285 of 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 e P. Shor. Restauração de estado quântico e tomografia de cópia única para estados fundamentais de hamiltonianos. Física. Rev. Lett., 105:190503, novembro de 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski e P. Shor. Dinheiro quântico de nós. Nos Anais da 3ª Conferência de Inovações em Ciência da Computação Teórica, páginas 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Dinheiro quântico com verificação clássica. Na 27ª Conferência Anual do IEEE sobre Complexidade Computacional, páginas 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser e YT Kalai. Sobre a impossibilidade de ofuscação com entrada auxiliar. No 46º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS 2005), 23-25 ​​de outubro de 2005, Pittsburgh, PA, EUA, Proceedings, páginas 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou e I. Kerenidis. Novas Construções para Dinheiro Quântico. Em S. Beigi e R. König, editores, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20-22 de maio de 2015, Bruxelas, Bélgica, volume 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. Os Fundamentos da Criptografia – Vol. 2, Aplicações Básicas. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler e T. Beth. Circuitos quânticos eficientes para códigos de correção de erros quânticos não Qubit. Interno. J. Encontrado. Computação. Ciência, 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz e Y. Lindell. Introdução à criptografia moderna, segunda edição. Imprensa CRC, 2014.

[32] NA Lynch. Algoritmos Distribuídos. Morgan Kaufmann, 1996.

[33] M. Mosca e D. Stebila. Moedas quânticas, volume 523 da Contemp. Matemática., páginas 35–47. Amer. Matemática. Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas e L. Perret. Criptoanálise não quântica da versão barulhenta do esquema de dinheiro quântico de Aaronson-Christiano. Segurança da Informação IET, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère e L. Perret. Criptoanálise algébrica de um esquema monetário quântico O caso livre de ruído. Em J. Katz, editor, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, EUA, 30 de março – 1 de abril de 2015, Proceedings, volume 9020 of Lecture Notes em Ciência da Computação, páginas 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasada. Contando subespaços de um espaço vetorial 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 e JI Cirac. Tokens quânticos tolerantes a ruído não falsificáveis. Anais da Academia Nacional de Ciências, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian e O. Sattath. Dinheiro Semi-Quantum. Em Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurique, Suíça, 21 a 23 de outubro de 2019, páginas 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian e O. Sattath. Dinheiro semiquântico. Journal of Cryptology, 35(2), janeiro de 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. Contratos Quantum Prudentes com Aplicações para Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Criptografia não clonável, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Dinheiro quântico de chave pública com um banco clássico. Em S. Leonardi e A. Gupta, editores, STOC '22: 54º Simpósio Anual ACM SIGACT sobre Teoria da Computação, Roma, Itália, 20 a 24 de junho de 2022, páginas 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Assinaturas tokenizadas semiquânticas. Em Y. Dodis e T. Shrimpton, editores, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Bárbara, CA, EUA, 15 a 18 de agosto de 2022, Proceedings, Part I, volume 13507 of Lecture Notas em Ciência da Computação, páginas 296–319. Primavera, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover e A. Patel. Um novo algoritmo para pesquisa quântica de ponto fixo. Informação Quântica e Computação, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto e N. Imoto. Dinheiro quântico anônimo. Na Conferência ERATO sobre Ciência da Informação Quântica, 2003.

[46] D. Unruh. Criptografia de liberação cronometrada quântica revogável. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Computação multipartidária eterna. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] S. Wiesner. Codificação conjugada. ACM Sigact News, 15(1):78-88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] WK Wootters e WH Zurek. Um único quantum não pode ser clonado. Natureza, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell e MJ Sellars. O núcleo nuclear opticamente endereçável gira em um sólido com tempo de coerência de seis horas. Nature, 517(7533):177–180, janeiro de 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. O relâmpago quântico nunca atinge o mesmo estado duas vezes, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. O relâmpago quântico nunca atinge o mesmo estado duas vezes. Ou: Dinheiro Quântico a partir de Suposições Criptográficas. 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 e P. Wallden, “Avanços na criptografia quântica”, Avanços em Óptica e Fotônica 12 4, 1012 (2020).

[2] Douglas Scott, “Paródias de ciência, pegadinhas de física e travessuras astronômicas”, arXiv: 2103.17057.

[3] Thomas Vidick e Tina Zhang, “Provas clássicas do conhecimento quântico”, arXiv: 2005.01691.

[4] Ou Sattath, “Contratos Quantum Prudentes com Aplicações para Bitcoin”, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry e Ruizhe Zhang, “Novas abordagens para proteção quântica contra cópia”, arXiv: 2004.09674.

[6] Roy Radian e Or Sattath, “Dinheiro Semiquântico”, arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser e Umesh Vazirani, “Criptografia negável em um mundo quântico”, arXiv: 2112.14988.

[8] Prabhanjan Ananth e Rolando L. La Placa, “Leasing de Software Seguro”, arXiv: 2005.05289.

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

[10] Andrea Coladangelo e Or Sattath, “Uma solução de dinheiro quântico para o problema de escalabilidade do Blockchain”, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery e Mark Zhandry, “Outra rodada de quebra e ganho de dinheiro quântico: como não construí-lo a partir de redes e muito mais”, arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu e Mark Zhandry, “Cossets ocultos e aplicativos para criptografia não clonável”, arXiv: 2107.05692.

[13] Ou Sattath, “Criptografia Inclonável”, arXiv: 2210.14265.

[14] Amit Behera e Or Sattath, “Moedas Quânticas Quase Públicas”, arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian e Hong-Sheng Zhou, “Rumo a memórias quânticas únicas de hardware sem estado”, arXiv: 1810.05226.

[16] Niraj Kumar, “Dinheiro quântico robusto praticamente viável com verificação clássica”, arXiv: 1908.04114.

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

[18] Nir Bitansky, Zvika Brakerski e Yael Tauman Kalai, “Reduções pós-quânticas construtivas”, arXiv: 2203.02314.

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-01-20 14:01:05). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2023-01-20 14:01:00).

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Carimbo de hora:

Mais de Diário Quântico