Skip to content
Voltar aos resultados

Criptografia Baseada em Reticulados

Proposto por
Miklós Ajtai
Ano
1996
Tipo
public-key cryptosystem based on lattice hardness
Família
Post-quantum cryptography

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Criptografia baseada em reticulados é uma classe de criptossistemas cuja segurança deriva da dificuldade computacional de problemas de reticulados, particularmente o problema do vetor mais curto (SVP) e o aprendizado com erros (LWE).

Propostas inicialmente por Miklós Ajtai em 1996, as abordagens baseadas em reticulados ganharam proeminência como os principais candidatos para criptografia pós-quântica. Diferentemente de RSA e ECC, que são vulneráveis a computadores quânticos, acredita-se que os problemas de reticulados permaneçam difíceis mesmo contra algoritmos quânticos.

A intuição por trás do método

Um reticulado é um subgrupo discreto do espaço Euclidiano formado por combinações lineares inteiras de vetores de base. A criptografia baseada em reticulados explora a lacuna entre dois problemas: encontrar um vetor curto em um reticulado é computacionalmente difícil, mas com informação adicional (uma base secreta), o vetor curto pode ser encontrado rapidamente. A criptografia de chave pública é construída publicando uma base difícil e mantendo uma base fácil em segredo. Adicionar um pequeno ruído aleatório (o paradigma de aprendizado com erros) fortalece ainda mais a segurança, fazendo o problema se assemelhar a um sistema linear ruidoso que é difícil de resolver.

História

O trabalho fundamental de Ajtai em 1996 conectou a dificuldade de reticulados à criptografia. O framework de aprendizado com erros (LWE) de Regev em 2005 forneceu uma base prática e versátil para a criptografia de reticulados. O campo acelerou após instituições acadêmicas e governamentais reconhecerem a ameaça da computação quântica à infraestrutura criptográfica atual. Em 2022, o NIST padronizou algoritmos criptográficos pós-quânticos, selecionando esquemas baseados em reticulados (CRYSTALS-Kyber para criptografia, CRYSTALS-Dilithium para assinaturas) como recomendações primárias.

Quando usar

A criptografia baseada em reticulados é essencial para sistemas projetados para permanecerem seguros contra futuros computadores quânticos. É recomendada para confidencialidade de longo prazo de dados sensíveis, comunicações governamentais e militares, e infraestrutura que deve permanecer segura por décadas. À medida que algoritmos pós-quânticos padronizados amadurecem (o NIST recentemente padronizou ML-KEM e ML-DSA), os métodos de reticulado estão se tornando mainstream em sistemas criptográficos modernos.

Limitações e considerações

  • Chaves e tamanhos de texto cifrado maiores em comparação com RSA ou ECC tradicionais, aumentando a sobrecarga de armazenamento e transmissão
  • Mais recente e menos amplamente implantado que RSA ou ECC, portanto, a experiência de implantação no mundo real é limitada
  • Alguns esquemas baseados em reticulados possuem escolhas de parâmetros sutis que afetam significativamente a segurança; parâmetros incorretos podem ser catastróficos

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Acredita-se ser resistente a ataques de computadores quânticos, incluindo o algoritmo de Shor
  • Fortes fundamentos matemáticos baseados em problemas de reticulados bem estudados
  • Suporta tanto criptografia quanto assinaturas digitais dentro do mesmo framework
  • Implementações práticas disponíveis com custos computacionais razoáveis para hardware moderno

Aplicações

  • Segurança de transporte pós-quântica para proteger comunicações contra futura decriptografia quântica
  • Criptografia de arquivamento de longo prazo para documentos e dados que devem permanecer secretos por décadas
  • Sistemas de comunicação governamentais e militares resilientes a ameaças quânticas
  • Sistemas de blockchain e criptomoedas projetados para segurança resistente a quântica
  • Sistemas de IoT e embarcados onde a resistência quântica é um requisito de projeto
  • Sistemas criptográficos híbridos combinando reticulados e algoritmos tradicionais durante o período de transição criptográfica

Como funciona

Como funciona

1

Escolha as dimensões do reticulado n, o módulo q e a distribuição de erro. Gere uma base curta secreta e derive uma base pública a partir dela usando transformações de reticulado.

2

A chave pública é derivada da base de reticulado difícil; ela não fornece informação sobre a base secreta de uma perspectiva computacional.

3

Para criptografar, adicione o texto plano a uma combinação linear ruidosa dos vetores da base pública, criando um ponto de reticulado mais ruído.

4

Usando a base curta secreta, reduza o ponto de reticulado ruidoso e extraia o texto plano.

Erros comuns

  • A seleção de parâmetros de reticulado (dimensão, módulo, distribuição de erro) não é trivial; o uso de parâmetros padrão aprovados pelo NIST é fortemente recomendado
  • Ataques de canal lateral (tempo, análise de energia) em operações de reticulado exigem implementação cuidadosa; algoritmos de tempo constante são essenciais
  • Misturar algoritmos baseados em reticulados e clássicos incorretamente pode criar sistemas híbridos com fraquezas inesperadas

Perguntas frequentes

Qual é o problema do aprendizado com erros (LWE)?

LWE é um problema computacional onde se recebe equações lineares ruidosas sobre um corpo finito. Dadas equações da forma a·x + e (mod q), onde a é aleatório, x é secreto e e é um ruído pequeno, recuperar x sem conhecer e é computacionalmente difícil.

Por que as chaves baseadas em reticulados são maiores que as chaves RSA?

Bases de reticulados e as matrizes que as codificam contêm mais informação do que um único número composto. Codificar uma base de reticulado criptograficamente requer mais bits, embora esquemas recentes tenham otimizado as representações.

Os problemas de reticulados são resistentes a quântica?

Não há nenhum algoritmo quântico conhecido que seja mais rápido que os algoritmos clássicos para problemas de reticulados como SVP ou LWE, embora esta permaneça uma área de pesquisa ativa. A dificuldade de reticulados é conjecturada para sobreviver a computadores quânticos.

Qual é a recomendação do NIST sobre criptografia de reticulados?

O NIST padronizou ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) para criptografia e ML-DSA (Module-Lattice-Based Digital Signature Algorithm) para assinaturas como algoritmos pós-quânticos primários nas FIPS 203 e FIPS 204.

Posso usar criptografia baseada em reticulados hoje?

Sim. Muitas bibliotecas criptográficas modernas agora suportam algoritmos de reticulados padronizados pelo NIST. Organizações que lidam com dados sensíveis com longos períodos de retenção devem iniciar o planejamento de migração.

Métodos relacionados

Fontes

  1. Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.

    Abrir referência da publicação
    Copiado.
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    Abrir referência da publicação
    Copiado.