Assinaturas CRYSTALS-Dilithium e Falcon

As assinaturas RSA e ECDSA são quebradas pelo algoritmo de Shor. As assinaturas pós-quânticas devem substituí-las em: certificados TLS, assinatura de código, assinatura de e-mails (S/MIME, PGP) e autenticação de atualizações de software. O NIST padronizou dois esquemas baseados em reticulados: ML-DSA e FN-DSA.

Dilithium baseia-se na dificuldade de Module-LWE e Module-SIS (Solução de Inteiros Curtos). A prova de segurança está no QROM (Modelo de Oráculo Aleatório Quântico). Há três variantes: Dilithium2 (aproximadamente 128 bits), Dilithium3 (aproximadamente 192 bits) e Dilithium5 (aproximadamente 256 bits). O caminho de assinatura é simples e não usa amostragem por rejeição.

Chave privada: matrizes secretas s1, s2. Chave pública: t = As1 + s2. Assine: extraia y aleatoriamente; calcule w = Ay; calcule o desafio c = H(mu || w1), em que w1 = HighBits(w); calcule z = y + cs1; se ||z|| ou ||r0|| for grande demais, rejeite e tente novamente. Produza (z, c, indicação).

Verifique (z, c, indicação): confirme que ||z|| é pequeno; calcule w' = Az - ct; use a indicação para recuperar w1; verifique c == H(mu || w1). A indicação é um pequeno número de bits obtido de MakeHint(). A rejeição garante que z não vaze s1 — o argumento de segurança é um argumento de "aborta-e-então-uniforme".

ML-DSA-65 (Dilithium3, segurança de 192 bits): chave pública de 1952 bytes, chave privada de 4000 bytes e assinatura de 3293 bytes. Compare com ECDSA-P256: chave pública de 64 bytes e assinatura de 64 bytes. As assinaturas do Dilithium são aproximadamente 40 a 50 vezes maiores, mas são seguras contra ataques quânticos.

Falcon baseia-se em reticulados NTRU e usa um amostrador gaussiano sobre o reticulado NTRU. As assinaturas são significativamente menores que as do Dilithium, mas a assinatura exige um amostrador gaussiano de ponto flutuante — mais difícil de implementar em tempo constante e mais complexo de programar com segurança.

Falcon-512 (segurança de 128 bits): chave pública de 897 bytes e assinatura de 666 bytes — muito menor que o Dilithium. Compromisso: Falcon é mais difícil de implementar com segurança, pois a amostragem gaussiana é suscetível a ataques de temporização. É adequado para ambientes com largura de banda limitada, mas exige uma implementação cuidadosa.

SPHINCS+ é um esquema de assinatura baseado em funções de resumo — uma escolha conservadora, sem premissas algébricas estruturais. A segurança depende apenas da segurança da função de resumo. Tamanho da assinatura: aproximadamente 8 a 50 KB, portanto grande. Assinatura lenta. É usado quando a confiança de longo prazo é fundamental e o desempenho é secundário.

ML-DSA (Dilithium): uso geral, implementação simples, adequado para certificados TLS e assinatura de código. FN-DSA (Falcon): ambientes com largura de banda limitada, como a Internet das Coisas e LPWAN. SLH-DSA (SPHINCS+): extremamente conservador, adequado para raízes de longa duração, como chaves CA desconectadas e a raiz de confiança de um software.

Dilithium: a amostragem por rejeição pode vazar a temporização de ramificações — use comparação em tempo constante. Falcon: o amostrador gaussiano usa ponto flutuante — garanta o determinismo de FP. Ambos: evite canais laterais na aritmética polinomial. Use as implementações de referência dos pacotes de submissão do NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Todos foram publicados em agosto de 2024. Bibliotecas: OpenSSL 3.x, BoringSSL e liboqs, do projeto Open Quantum Safe, implementam os três.

Qual é a principal vantagem do Falcon em relação ao Dilithium?

ML-DSA (Dilithium): baseado em reticulados, simples, assinaturas de aproximadamente 3 KB. FN-DSA (Falcon): baseado em NTRU, assinaturas de aproximadamente 700 bytes, implementação complexa. SLH-DSA (SPHINCS+): baseado em funções de resumo, conservador, grande. Todos foram padronizados nos FIPS 204/205/206. A seguir: migração para PQC com abordagens híbridas.