Criptografia baseada em rede - Lattice-based cryptography

Criptografia baseada em reticulado é o termo genérico para construções de primitivas criptográficas que envolvem reticulados , seja na própria construção ou na prova de segurança. As construções baseadas em reticulado são atualmente candidatos importantes para a criptografia pós-quântica . Ao contrário dos esquemas de chave pública mais amplamente usados ​​e conhecidos, como RSA , Diffie-Hellman ou criptossistemas de curva elíptica , que poderiam, teoricamente, ser facilmente atacados por um computador quântico , algumas construções baseadas em rede parecem ser resistentes ao ataque de ambos computadores clássicos e quânticos. Além disso, muitas construções baseadas em rede são consideradas seguras sob a suposição de que certos problemas de rede computacional bem estudados não podem ser resolvidos de forma eficiente.

História

Em 1996, Miklós Ajtai introduziu a primeira construção criptográfica baseada em rede, cuja segurança poderia ser baseada na dureza de problemas de rede bem estudados, e Cynthia Dwork mostrou que um certo problema de rede de caso médio, conhecido como Short Integer Solutions (SIS), é pelo menos tão difícil de resolver quanto um problema de rede de pior caso . Ela então mostrou uma função hash criptográfica cuja segurança é equivalente à dureza computacional do SIS.

Em 1998, Jeffrey Hoffstein , Jill Pipher e Joseph H. Silverman introduziram um esquema de criptografia de chave pública baseado em rede , conhecido como NTRU . No entanto, seu esquema não é conhecido por ser pelo menos tão difícil quanto resolver um problema de rede de pior caso.

O primeiro esquema de criptografia de chave pública baseado em rede, cuja segurança foi comprovada sob as suposições de dureza do pior caso, foi introduzido por Oded Regev em 2005, junto com o problema de Aprendizagem com Erros (LWE). Desde então, muito trabalho de acompanhamento se concentrou em melhorar a prova de segurança do Regev e melhorar a eficiência do esquema original. Muito mais trabalho foi dedicado à construção de primitivas criptográficas adicionais com base em LWE e problemas relacionados. Por exemplo, em 2009, Craig Gentry introduziu o primeiro esquema de criptografia totalmente homomórfico , baseado em um problema de rede.

Fundo matemático

Uma rede é o conjunto de todas as combinações lineares inteiras de vetores de base . Ou seja, por exemplo, é uma rede, gerada pela base ortonormal padrão para . Crucialmente, a base para uma rede não é única. Por exemplo, os vectores , e formar uma base alternativa para .

O problema computacional baseado em rede mais importante é o Problema do Vetor Mais Curto (SVP ou às vezes GapSVP), que nos pede para aproximar o comprimento euclidiano mínimo de um vetor de rede diferente de zero. Este problema é considerado difícil de resolver de forma eficiente, mesmo com fatores de aproximação polinomiais em , e mesmo com um computador quântico. Muitas (embora não todas) construções criptográficas baseadas em rede são conhecidas por serem seguras se o SVP for de fato difícil neste regime.

Criptossistemas selecionados baseados em rede

Esquemas de criptografia

Assinaturas

Funções de hash

  • SWIFFT
  • LASH (função hash baseada em rede)

Criptografia totalmente homomórfica

Veja também: Criptografia totalmente homomórfica
  • Esquema original de Gentry.
  • Brakerski e Vaikuntanathan.

Segurança

As construções criptográficas baseadas em rede são as principais candidatas para a criptografia pós-quântica de chave pública . De fato, as principais formas alternativas de criptografia de chave pública são esquemas baseados na dureza da fatoração e problemas relacionados e esquemas baseados na dureza do logaritmo discreto e problemas relacionados . No entanto, tanto a fatoração quanto o logaritmo discreto são conhecidos por serem solucionáveis ​​em tempo polinomial em um computador quântico . Além disso, algoritmos para fatoração tendem a produzir algoritmos para logaritmos discretos e vice-versa. Isso motiva ainda mais o estudo de construções baseadas em hipóteses alternativas, como a dureza de problemas de rede.

Muitos esquemas criptográficos baseados em rede são conhecidos por serem seguros assumindo o pior caso de dureza de certos problemas de rede. Ou seja, se existe um algoritmo que pode quebrar com eficiência o esquema criptográfico com probabilidade não desprezível, então existe um algoritmo eficiente que resolve um certo problema de rede em qualquer entrada. Em contraste, os esquemas criptográficos baseados em, por exemplo, a fatoração seriam quebrados se a fatoração fosse fácil "em uma entrada média ", mesmo se a fatoração fosse de fato difícil no pior caso. No entanto, para as construções baseadas em rede mais eficientes e práticas (como esquemas baseados em NTRU e até mesmo esquemas baseados em LWE com parâmetros mais agressivos), tais resultados de pior caso de dureza não são conhecidos. Para alguns esquemas, resultados de pior caso de dureza são conhecidos apenas para certas redes estruturadas ou não.

Funcionalidade

Para muitas primitivas criptográficas, as únicas construções conhecidas são baseadas em reticulados ou objetos intimamente relacionados. Essas primitivas incluem criptografia totalmente homomórfica , ofuscação indistinguível , mapas criptográficos multilineares e criptografia funcional .

Veja também

Referências

  1. ^ a b Ajtai, Miklós (1996). "Generating Hard Instances of Lattice Problems". Anais do Vigésimo Oitavo Simpósio Anual de ACM em Teoria da Computação . pp. 99–108. CiteSeerX   10.1.1.40.2489 . doi : 10.1145 / 237814.237838 . ISBN   978-0-89791-785-8 . S2CID   6864824 .
  2. ^ Criptossistema de chave pública com equivalência de pior caso / caso médio
  3. ^ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: Um criptosistema de chave pública baseado em anel". Teoria Algorítmica dos Números . Notas de aula em Ciência da Computação. 1423 . pp. 267–288. CiteSeerX   10.1.1.25.8422 . doi : 10.1007 / bfb0054868 . ISBN   978-3-540-64657-0 .
  4. ^ a b Regev, Oded (2005-01-01). "Em redes, aprendizagem com erros, códigos lineares aleatórios e criptografia". Anais do trigésimo sétimo simpósio anual da ACM em Teoria da Computação - STOC '05 . ACM. pp. 84–93. CiteSeerX   10.1.1.110.4776 . doi : 10.1145 / 1060590.1060603 . ISBN   978-1581139600 . S2CID   53223958 .
  5. ^ a b Peikert, Chris (01-01-2009). "Criptossistemas de chave pública do problema de menor vetor de pior caso". Anais do 41º simpósio anual da ACM sobre Simpósio de teoria da computação - STOC '09 . ACM. pp. 333–342. CiteSeerX   10.1.1.168.270 . doi : 10.1145 / 1536414.1536461 . ISBN   9781605585062 . S2CID   1864880 .
  6. ^ Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (01-01-2013). “Dureza clássica de aprender com erros”. Anais do 45º simpósio anual da ACM sobre Simpósio de teoria da computação - STOC '13 . ACM. pp. 575–584. arXiv : 1306.0281 . doi : 10.1145 / 2488608.2488680 . ISBN   9781450320290 . S2CID   6005009 .
  7. ^ a b Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (30/05/2010). Sobre redes ideais e aprendizado com erros sobre anéis . Avanços em Criptologia - EUROCRYPT 2010 . Notas de aula em Ciência da Computação. 6110 . pp. 1–23. CiteSeerX   10.1.1.352.8218 . doi : 10.1007 / 978-3-642-13190-5_1 . ISBN   978-3-642-13189-9 .
  8. ^ a b Peikert, Chris (2014-07-16). "Criptografia Lattice para a Internet" (PDF) . IACR . Recuperado em 11/01/2017 .
  9. ^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (01-01-2015). "Troca de chave pós-quântica - uma nova esperança" . Citar diário requer |journal= ( ajuda )
  10. ^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (01/01/2016). "Frodo: Tire o anel! Troca de Chaves Prática e Quantum-Secure da LWE" . Citar diário requer |journal= ( ajuda )
  11. ^ a b c Gentry, Craig (2009-01-01). A Fully Homomorphic Encryption Scheme (Thesis). Stanford, CA, EUA: Stanford University.
  12. ^ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems" (PDF) . Hardware criptográfico e sistemas embarcados - CHES 2012 . Notas de aula em Ciência da Computação. 7428 . IACR. pp. 530–547. doi : 10.1007 / 978-3-642-33027-8_31 . ISBN   978-3-642-33026-1 . Recuperado em 11/01/2017 .
  13. ^ "LASH: uma função hash baseada em rede" . Arquivado do original em 16 de outubro de 2008 . Página visitada em 31/07/2008 . CS1 maint: bot: status do URL original desconhecido ( link ) (quebrado)
  14. ^ Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling e Huaxiong Wang (2008). "Cryptanalysis of LASH" (PDF) . Criptografia rápida de software . Notas de aula em Ciência da Computação. 5086 . pp. 207–223. doi : 10.1007 / 978-3-540-71039-4_13 . ISBN   978-3-540-71038-7 . CS1 maint: usa o parâmetro de autores ( link )
  15. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2011). "Criptografia totalmente homomórfica eficiente de LWE (padrão)" . Citar diário requer |journal= ( ajuda )
  16. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2013). "FHE baseado em rede tão seguro quanto PKE" . Citar diário requer |journal= ( ajuda )
  17. ^ Micciancio, Daniele; Regev, Oded (22/07/2008). "Criptografia baseada em rede" (PDF) . Recuperado em 11/01/2017 . Citar diário requer |journal= ( ajuda )
  18. ^ Shor, Peter W. (01/10/1997). "Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico". SIAM Journal on Computing . 26 (5): 1484-1509. arXiv : quant-ph / 9508027 . doi : 10.1137 / S0097539795293172 . ISSN   0097-5397 . S2CID   2337707 .
  19. ^ a b Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (01-01-2013). "Ofuscação de indistinguibilidade do candidato e criptografia funcional para todos os circuitos" . CiteSeerX   10.1.1.400.6501 . Citar diário requer |journal= ( ajuda )

Bibliografia

  • Oded Goldreich, Shafi Goldwasser e Shai Halevi. "Criptossistemas de chave pública de problemas de redução de rede". Em CRYPTO '97: Proceedings of the 17th Annual Cryptology Conference on Advances in Cryptology , páginas 112–131, London, UK, 1997. Springer-Verlag.
  • Phong Q. Nguyen. "Criptoanálise do criptosistema Goldreich-Goldwasser-Halevi da criptografia '97". Em CRYPTO '99: Proceedings of the 19th Annual Cryptology Conference on Advances in Cryptology , pages 288–304, London, UK, 1999. Springer-Verlag.
  • Oded Regev. Criptografia baseada em rede. Em Advances in cryptology (CRYPTO) , páginas 131-141, 2006.