Criptografia baseada em reticulados é 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. Construções baseadas em reticulados suportam padrões importantes de criptografia pós-quântica. Diferentemente de esquemas de chave pública mais amplamente usados e conhecidos, como RSA, Diffie-Hellman ou criptossistemas de curva elíptica — que poderiam, teoricamente, ser derrotados usando o algoritmo de Shor em um computador quântico — algumas construções baseadas em reticulados parecem ser resistentes a ataques tanto de computadores clássicos quanto quânticos. Além disso, muitas construções baseadas em reticulados são consideradas seguras sob a suposição de que certos problemas de reticulado bem estudados não podem ser resolvidos eficientemente.

Em 2024, o NIST anunciou o Padrão de Assinatura Digital Baseada em Reticulado de Módulo para criptografia pós-quântica.

História Em 1996, Miklós Ajtai introduziu a primeira construção criptográfica baseada em reticulados cuja segurança poderia ser baseada na dificuldade de problemas de reticulado bem estudados, e Cynthia Dwork mostrou que um certo problema de reticulado em média, conhecido como soluções inteiras curtas (SIS), é pelo menos tão difícil de resolver quanto um problema de reticulado de pior caso.Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. Ela então mostrou uma função hash criptográfica cuja segurança é equivalente à dificuldade computacional do SIS.

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

O primeiro esquema de criptografia de chave pública baseado em reticulados cuja segurança foi provada sob hipóteses de dificuldade de pior caso foi introduzido por Oded Regev em 2005, juntamente com o problema learning with errors (LWE). Desde então, muito trabalho subsequente focou em melhorar a prova de segurança de Regev e melhorar a eficiência do esquema original. Muito mais trabalho foi dedicado à construção de primitivas criptográficas adicionais baseadas em LWE e problemas relacionados. Por exemplo, em 2009, Craig Gentry introduziu o primeiro esquema de criptografia totalmente homomórfica, que era baseado em um problema de reticulado.

Fundamentos matemáticos Em álgebra linear, um reticulado é o conjunto de todas as combinações lineares inteiras de vetores de uma base de . Em outras palavras,

Por exemplo, é um reticulado, gerado pela base canônica para . Crucialmente, a base de um reticulado não é única. Por exemplo, os vetores , e formam uma base alternativa para .

O problema computacional baseado em reticulados mais importante é o problema do vetor mais curto (SVP ou às vezes GapSVP), que pede um comprimento euclidiano mínimo aproximado de um vetor de reticulado não nulo. Acredita-se que este problema seja difícil de resolver eficientemente, mesmo com fatores de aproximação que são polinomiais em , e mesmo com um computador quântico. Muitas (embora não todas) construções criptográficas baseadas em reticulados são conhecidas por serem seguras se o SVP for de fato difícil neste regime.

Esquemas baseados em reticulados selecionados Esta seção apresenta esquemas baseados em reticulados selecionados, agrupados por primitiva.

Criptografia Esquemas selecionados para fins de criptografia:

Esquema de criptografia GGH, que é baseado no problema do vetor mais próximo (CVP). Em 1999, Nguyen publicou uma falha crítica no design do esquema.NGUYEN, Phon. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from crypto '97. In Crypto '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag. NTRUEncrypt.

Criptografia homomórfica Esquemas selecionados para fins de criptografia homomórfica:

Esquema original de Gentry. Brakerski e Vaikuntanathan.

Funções hash Esquemas criptográficos baseados em reticulados selecionados para fins de hash:

SWIFFT. Função Hash Baseada em Reticulados (LASH).

Troca de chaves Esquemas selecionados para fins de troca de chaves, também chamada de estabelecimento de chaves, encapsulamento de chaves e mecanismo de encapsulamento de chaves (KEM):

CRYSTALS-Kyber,AVANZI, R. et al. CRYSTALS-KYBER Algorithm Specifications And Supporting Documentation. CRYSTALS Team, 2021. Disponível na Internet em <https://www.pq-crystals.org/>, acessado em 4 de novembro de 2022. que é construído sobre aprendizado com erros de módulo (module-LWE). Kyber foi selecionado para padronização pelo NIST em 2023. Em agosto de 2023, o NIST publicou o FIPS 203 (Rascunho Inicial Público) e começou a se referir à sua versão do Kyber como Mecanismo de Encapsulamento de Chaves Baseado em Reticulado de Módulo (ML-KEM).Raimondo, Gina M., and Locascio, Laurie E., FIPS 203 (Draft) Federal Information Processing Standards Publication – Module-Lattice-based Key-Encapsulation Mechanism Standard. August 24, 2023. Information Technology Laboratory, National Institute of Standards and Technology. Gaithersburg, MD, United States of America. . Disponível na Internet em <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf>, acessado em 30 de outubro de 2023. FrodoKEM,FrodoKEM team. FrodoKEM. 2022. Disponível na Internet em <https://frodokem.org/>, acessado em 2 de novembro de 2022.ALKIM, E. et al. FrodoKEM learning with errors key encapsulation algorithm specifications and supporting documentation. 2020. Disponível na Internet em <https://frodokem.org/files/FrodoKEM-specification-20200930.pdf>, acessado em 1 de novembro de 2022 um esquema baseado no problema learning with errors (LWE). FrodoKEM juntou-se à chamada de padronização conduzida pelo National Institute of Standards and Technology (NIST),CSRC, National Institute of Standards and Technology. Post-Quantum Cryptography. 2019. Disponível na Internet em <https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/>, acessado em 2 de novembro de 2022. e sobreviveu até a 3ª rodada do processo. Foi então descartado devido a problemas de baixo desempenho. Em outubro de 2022, a conta do Twitter associada ao criptólogo Daniel J. Bernstein publicou problemas de segurança no frodokem640.Bernstein, Daniel J. FrodoKEM documentation claims that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin". Warning: That's not true. Send 2^40 ciphertexts to a frodokem640 public key; one of them will be decrypted by a large-scale attack feasible today. 2022. Disponível na Internet em <https://twitter.com/hashbreaker/status/1587184970258255872>, acessado em 2 de novembro de 2022. NewHope é baseado no problema ring learning with errors (RLWE).SCHWABE, Peter et al. NewHope's Web site. 2022. Disponível na Internet em <https://newhopecrypto.org/>, acessado em 6 de dezembro de 2022. NTRU Prime.Bernstein, Daniel J. et al., NTRU Prime: round 3. 2020. Disponível na Internet em <https://ntruprime.cr.yp.to/>, acessado em 8 de novembro de 2022. Trabalho de Peikert, que é baseado no problema ring learning with errors (RLWE). Saber,D'ANVERS, Jan-Pieter, KARMAKAR, Angshuman, ROY, Sujoy Sinha, and VERCAUTEREN, Frederik. Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. 2018. Disponível na Internet em <https://eprint.iacr.org/2018/230>, acessado em 5 de novembro de 2022. que é baseado no problema module learning with rounding (module-LWR).

Assinatura Esta seção lista uma seleção de esquemas baseados em reticulados para fins de assinaturas digitais.

CRYSTALS-Dilithium,BAI, S. et al. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). CRYSTALS Team, 2021. Disponível na Internet em <https://www.pq-crystals.org/>, acessado em 2 de novembro de 2021.SEILER, Gregor et al. pq-crystals/dilithium (Dilithium at GitHub), 2022. Disponível na Internet em <https://github.com/pq-crystals/dilithium>, acessado em 29 de dezembro de 2022. que é construído sobre aprendizado com erros de módulo (module-LWE) e solução inteira curta de módulo (module-SIS). Dilithium foi selecionado para padronização pelo NIST. De acordo com uma mensagem de Ray Perlner, escrevendo em nome da equipe NIST PQC, o padrão de assinatura module-LWE do NIST deve ser baseado na versão 3.1 da especificação do Dilithium.

Falcon, que é construído sobre solução inteira curta (SIS) sobre NTRU. Falcon foi selecionado para padronização pelo NIST.FOUQUE, Pierre-Alain et al. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. 2020. Disponível na Internet em <https://falcon-sign.info/>, acessado em 8 de novembro de 2020. Esquema de assinatura GGH. Trabalho de Güneysu, Lyubashevsky e Pöppelmann, que é baseado em ring learning with errors (RLWE). MITAKA, uma variante do Falcon.ESPITAU, Thomas et al. MITAKA: A Simpler, Parallelizable, Maskable Variant of Falcon. 2021. NTRUSign. qTESLA, que é baseado em ring learning with errors (RLWE). O esquema qTESLA juntou-se à chamada de padronização conduzida pelo National Institute of Standards and Technology (NIST).ALKIM, E. et al. The Lattice-Based Digital Signature Scheme qTESLA. IACR, 2019. Cryptology ePrint Archive, Report 2019/085. Disponível na Internet em <https://eprint.iacr.org/2019/085>, acessado em 1 de novembro de 2022.

CRYSTALS-Dilithium CRYSTALS-Dilithium ou simplesmente Dilithium é construído sobre module-LWE e module-SIS. Dilithium foi selecionado pelo NIST como base para um padrão de assinatura digital. De acordo com uma mensagem de Ray Perlner, escrevendo em nome da equipe NIST PQC, o padrão de assinatura module-LWE do NIST deve ser baseado na versão 3.1 da especificação do Dilithium. As mudanças do NIST no Dilithium 3.1 pretendem suportar aleatoriedade adicional na assinatura (hedged signing) e outras melhorias.Perlner, Ray A.. Planned changes to the Dilithium spec. April 20th, 2023. Google Groups. Disponível na Internet em <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/3pBJsYjfRw4/m/GjJ2icQkAQAJ>, acessado em 14 de junho de 2023.

Dilithium foi um dos dois esquemas de assinatura digital inicialmente escolhidos pelo NIST em seu processo de criptografia pós-quântica, sendo o outro o SPHINCS+, que não é baseado em reticulados, mas em hashes.

Em agosto de 2023, o NIST publicou o FIPS 204 (Rascunho Inicial Público) e começou a chamar o Dilithium de "Algoritmo de Assinatura Digital Baseado em Reticulado de Módulo" (ML-DSA).Raimondo, Gina M., and Locascio, Laurie E., FIPS 204 (Draft) Federal Information Processing Standards Publication – Module-Lattice-Based Digital Signature Standard. August 24, 2023. Information Technology Laboratory, National Institute of Standards and Technology. Gaithersburg, MD, United States of America. . Disponível na Internet em <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf>, acessado em 2 de setembro de 2023.

Em outubro de 2023, o ML-DSA estava sendo implementado como parte do Libgcrypt, de acordo com Falko Strenzke.Gcrypt-devel mailing list. Dilithium Implementation in Libgcrypt. October 24th, 2023. Disponível na Internet em <https://lists.gnupg.org/pipermail/gcrypt-devel/2023-October/005572.html>, acessado em 24 de outubro de 2023.

Em agosto de 2024, o NIST padronizou oficialmente o CRYSTALS-Dilithium sob o nome ML-DSA, estabelecendo-o como o padrão primário (FIPS 204) para assinaturas digitais resistentes a quantum.

Segurança