Firmas CRYSTALS-Dilithium y Falcon

Las firmas RSA y ECDSA quedan comprometidas por el algoritmo de Shor. Las firmas poscuánticas deben sustituirlas en los certificados TLS, la firma de código, la firma de correo electrónico (S/MIME, PGP) y la autenticación de actualizaciones de software. NIST estandarizó dos esquemas basados en retículas: ML-DSA y FN-DSA.

Dilithium se basa en la dificultad de Module-LWE y Module-SIS (Short Integer Solution). Su demostración de seguridad se realiza en el QROM (Quantum Random Oracle Model). Tiene tres variantes: Dilithium2 (~128 bits), Dilithium3 (~192 bits) y Dilithium5 (~256 bits). Su ruta de firma es sencilla y no requiere muestreo por rechazo.

Clave privada: matrices secretas s1, s2. Clave pública: t = As1 + s2. Para firmar, muestree un valor aleatorio y; calcule w = Ay; calcule el desafío c = H(mu || w1), donde w1 = HighBits(w); calcule z = y + cs1; si ||z|| o ||r0|| es demasiado grande, rechace y vuelva a intentarlo. Produzca (z, c, hint).

Verifique (z, c, hint): compruebe que ||z|| sea pequeño; calcule w' = Az - ct; utilice hint para recuperar w1; verifique c == H(mu || w1). hint es un número pequeño de bits obtenido de MakeHint(). El rechazo garantiza que z no filtre s1; el argumento de seguridad es un argumento "aborts-then-uniform".

ML-DSA-65 (Dilithium3, seguridad de 192 bits): clave pública de 1952 bytes, clave privada de 4000 bytes y firma de 3293 bytes. En comparación, ECDSA-P256 utiliza una clave pública de 64 bytes y una firma de 64 bytes. Las firmas de Dilithium son aproximadamente entre 40 y 50 veces más grandes, pero ofrecen seguridad poscuántica.

Falcon se basa en retículas NTRU y utiliza un muestreador gaussiano sobre la retícula NTRU. Sus firmas son considerablemente más pequeñas que las de Dilithium, pero la firma requiere un muestreador gaussiano de coma flotante, que es más difícil de implementar en tiempo constante y complica la escritura de código seguro.

Falcon-512 (seguridad de 128 bits): clave pública de 897 bytes y firma de 666 bytes, mucho más pequeñas que las de Dilithium. La contrapartida es que Falcon es más difícil de implementar de forma segura (el muestreo gaussiano es susceptible a ataques temporales). Es adecuado para entornos con ancho de banda limitado, pero requiere una implementación cuidadosa.

SPHINCS+ es un esquema de firma basado en hashes, una opción conservadora que no depende de supuestos algebraicos estructurales. La seguridad depende únicamente de la seguridad de la función hash. Tamaño de la firma: aproximadamente entre 8 y 50 KB (grande). La firma es lenta. Se utiliza cuando la confianza a largo plazo es fundamental y el rendimiento es secundario.

ML-DSA (Dilithium): propósito general, implementación sencilla y adecuado para certificados TLS y firma de código. FN-DSA (Falcon): entornos con ancho de banda limitado (IoT, LPWAN). SLH-DSA (SPHINCS+): opción muy conservadora para raíces de larga duración (claves sin conexión de la CA y raíz de confianza del software).

Dilithium: el muestreo por rechazo puede filtrar información mediante el tiempo de ejecución de las ramas; utilice comparaciones en tiempo constante. Falcon: el muestreador gaussiano utiliza coma flotante; garantice el determinismo de la coma flotante. En ambos casos, evite los canales laterales en la aritmética polinómica. Utilice las implementaciones de referencia de los paquetes de propuestas de NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Todos se publicaron en agosto de 2024. Las bibliotecas OpenSSL 3.x, BoringSSL y liboqs (del proyecto Open Quantum Safe) implementan los tres.

¿Cuál es la principal ventaja de Falcon frente a Dilithium?

ML-DSA (Dilithium): basado en retículas, sencillo y con firmas de aproximadamente 3 KB. FN-DSA (Falcon): basado en NTRU, con firmas de aproximadamente 700 bytes y una implementación compleja. SLH-DSA (SPHINCS+): basado en hashes, conservador y grande. Todos están estandarizados en FIPS 204/205/206. Siguiente tema: migración a PQC mediante enfoques híbridos.