HQC: Un nuevo estándar de criptografía post-cuántica basado en códigos
- José Darío Flórez Gómez
- 30 jul
- 10 Min. de lectura
Este artículo presenta una revisión técnico divulgativa del algoritmo HQC (Hamming Quasi- Cyclic), recientemente estandarizado por el NIST como esquema de cifrado post-cuántico. Se describen los fundamentos matemáticos de la criptografía basada en códigos, la construcción detallada de HQC, el problema computacional subyacente de decodificación de síndromes en códigos quasi-cíclicos, y el impacto de su estandarización con una comparativa frente a Kyber.
La criptografía post-cuántica (PQC) busca esquemas criptográficos resistentes a los ataques de futuros computadores cuánticos. Dentro de las diversas familias de algoritmos PQC, una de las más veteranas es la criptografía basada en códigos, originada en 1978 con el criptosistema de McEliece [1]. Este enfoque emplea códigos de corrección de errores para construir sistemas de cifrado de clave pública.
En términos simples, se aprovecha la capacidad de ciertos códigos para detectar y corregir errores en mensajes, usando esto como base de un esquema criptográfico: el mensaje se transforma en una palabra código válida y luego se añaden errores aleatorios (bit flips) antes de transmitirla.
Solo quien posea la clave secreta (es decir, el conocimiento especial para decodificar ese código y corregir los errores) podrá recuperar el mensaje original.
En cambio, un adversario, se enfrenta al problema de corregir errores sin conocer la estructura del código, algo computacionalmente intratable para códigos suficientemente grandes [2].
Ejemplo ilustrativo.
Supongamos un código corrector sencillo que codifica palabras de 4 bits en palabras de 7 bits añadiendo bits de paridad (similar a un código de Hamming). Si queremos cifrar el mensaje 1011, primero lo codificamos obteniendo, digamos, 1011010 como palabra de código. Luego alteramos aleatoriamente algunos bits (errores) antes de enviarlo por ejemplo cambiando el tercer bit y obteniendo el criptograma 1001010.
A primera vista, este texto cifrado parece una secuencia de bits sin sentido; sin embargo, quien conozca el código usado puede detectar y corregir el error (ajustando el bit alterado) y recuperar 1011010, y de ahí el mensaje original 1011.
Para un atacante sin ese conocimiento, decodificar el criptograma es tan complejo como probar combinaciones de bits hasta dar con una palabra válida, un problema que crece exponencialmente con la longitud del código. De hecho, resolver la decodificación de códigos lineales generales es un problema NP-completo en el caso general [8], lo que cimenta la seguridad de estos sistemas incluso frente a computadoras cuánticas conocidas.
Criptografía basada en códigos: conceptos y antecedentes
La idea de usar códigos correctores de errores en criptografía fue propuesta por Robert McEliece en 1978, empleando códigos algebraicos (Goppa) para construir un cifrado de clave pública. La seguridad se basa en la dificultad de decodificar (encontrar el vector de errores) sin la clave secreta. En el esquema de McEliece clásico, la clave pública es esencialmente una matriz generadora de un código lineal algebraico oculto por transformaciones aleatorias, y la clave privada permite corregir hasta cierto número de errores.
Uno de los inconvenientes tradicionales de esta familia ha sido el tamaño grande de las claves: por ejemplo, en McEliece las claves públicas y privadas pueden ser del orden de cientos de kilobytes o incluso megabytes [1], lo que dificultó su adopción práctica.
No obstante, estos sistemas han resistido décadas de criptanálisis; de hecho, el McEliece clásico sigue intacto tras más de 40 años, por lo que la criptografía de códigos se considera una apuesta conservadora y segura en el mundo post-cuántico.
Con el avance de la investigación en códigos, aparecieron variantes que buscan reducir el tamaño de clave aprovechando estructuras especiales en los códigos. En particular, surgieron códigos quasi-cíclicos y códigos MDPC (Moderate Density Parity-Check) que introducen patrones repetitivos (estructura cíclica) en la matriz del código para reducir drásticamente la longitud de la clave pública sin debilitar demasiado la seguridad.
Por ejemplo, los esquemas BIKE y HQC, propuestos en el marco de la competencia de estandarización PQC del NIST, emplean códigos lineales binarios quasi-cíclicos de alta densidad, donde grandes matrices de paridad se representan con unos pocos vectores generadores circulantes. Esta estructura permite que la clave pública sea mucho más compacta que en McEliece clásico (que usaba códigos Goppa aleatorizados) [5, 3].
El algoritmo post-cuántico HQC (Hamming Quasi-Cyclic)
HQC es un esquema de cifrado de clave pública (KEM) basado en códigos que fue seleccionado por el NIST como nuevo estándar post-cuántico en marzo de 2025 [4]. Aprovecha las ventajas estructurales de los códigos lineales binarios cuasi-cíclicos, y su nombre “Hamming Quasi-Cyclic” alude a que trabaja sobre la métrica de Hamming (errores binarios) y utiliza códigos quasi-cíclicos.
A diferencia de McEliece, HQC no oculta la familia de códigos utilizada: la matriz generadora del código empleado es pública [2]. Su seguridad no depende de mantener secreto el código, sino de la dificultad de ciertos problemas de decodificación asociados a códigos aleatorios estructurados.
Componentes clave
Tipo de código y estructuraHQC: utiliza un híbrido de dos códigos clásicos concatenados: un código decodificable C de longitud n y dimensión k (por ejemplo, combinaciones de Reed–Muller y Reed–Solomon) capaz de corregir hasta Δ errores, integrado en un código de longitud 2n con estructura de doble circulante cuya matriz de paridad es (1 | h). La clave pública incluye la descripción de C (matriz generadora G) y el vector h, y la clave privada contiene dos vectores (x, y) de longitud n y peso Hamming bajo. A partir de ellos se calcula el vector público
s = x + h · y en F2[X]/(Xn − 1).
Problema difícil subyacente: La seguridad de HQC se basa en el QCSD (Quasi-Cyclic Syndrome Decoding): dado un síndrome s = H eT producido por un código quasi-cíclico de paridad H = (1, h) y un vector de error e de peso bajo, resulta computacionalmente infactible recuperar e sin información secreta.
Este problema es una variante estructurada del clásico SD (Syndrome Decoding), conocido por ser NP-completo [8]. En HQC no se introduce ninguna trampilla oculta en el código; la seguridad se reduce a la dificultad de SD en códigos quasi-cíclicos, ofreciendo así una estructura transparente apta para análisis formal [2].
Por supuesto, todo esquema de cifrado basado en errores debe lidiar con la posibilidad de fallos de decodificación (cuando el ruido supera la capacidad correctora). HQC se diseñó cuidadosamente para minimizar esta probabilidad de error de descifrado (DFR, Decryption Failure Rate).
De hecho, NIST destacó que HQC logró un DFR estimado extremadamente bajo (del orden de < 2−128) cumpliendo con nivel de seguridad IND-CCA2, superando a otro candidato como BIKE cuyo análisis de DFR permaneció incierto [4, 3]. Esto significa que es prácticamente nula la probabilidad de que un mensaje cifrado válido no pueda descifrarse con la clave correcta debido a errores en exceso.
Cifrado y descifrado (visión de alto nivel): El esquema HQC se implementa típicamente como un KEM, pero su núcleo de cifrado puede describirse de forma simplificada:
1. Clave pública: (h, s) y la matriz generadora G del código C.
2. Clave privada: (x, y) vectores secretos de peso bajo. Para cifrar un mensaje m de k bits:
3. Codificación y aleatorización: Se calcula mG ∈ Fn2,
y se generan aleatoriamente dos vectores r1, r2 de peso wr y un vector de error e de peso we [2].
4. Cálculo de componentes del cifrado: u = r1+h· r2, v = Trunc (mG+s · r2+e )
El par cifrado resultante es c = (u, v) [2].
5. Descifrado: Con la clave (x, y) el receptor calcula
v′ = v − u · y = mG + e − r1 y,
y aplica el decodificador de C para recuperar m [2].
Impacto de la estandarización y comparación con Kyber (ML-KEM) y otros algoritmos
La estandarización de HQC por parte del NIST en 2025 es un hito importante en la criptografía post-cuántica. HQC se convierte así en el quinto algoritmo PQC seleccionado por NIST para su portafolio de estándares, y el segundo KEM junto a Kyber (rebautizado en estándar como ML-KEM) [7].
A grandes rasgos, Kyber (ML-KEM) es un esquema basado en retículos euclidianos modulares elegido por su excelente desempeño y seguridad basada en problemas de lattice altamente estudiados [6]. HQC, en cambio, representa una línea matemática distinta (códigos) y fue seleccionado como “algoritmo de respaldo” para cifrado general [4].
Dustin Moody, criptógrafo líder del proyecto PQC de NIST, explicó que se busca tener dos enfoques independientes en caso de que en el futuro se encuentre alguna debilidad en uno de ellos [5]. De este modo, HQC añade redundancia y diversidad al arsenal criptográfico: si algún avance cuántico o matemático debilitara la seguridad de los retículos estructurados (en los que se basa Kyber), los códigos correctores servirían como alternativa resistente.
Comparativa con Kyber (ML-KEM)
NIST deja claro que HQC no pretende reemplazar a Kyber, el cual permanece como KEM principal por su eficiencia y amplia compatibilidad [3]. Kyber ofrece cifrado/descifrado muy rápidos y tamaños de clave y ciphertext pequeños; por ejemplo, una clave pública de Kyber-768 (seguridad clásica ∼ 192 bits) es de aproximadamente 1184 bytes y el ciphertext de unos 1088 bytes [6].
En HQC de nivel de seguridad equivalente (∼ 192 bits), la clave pública ronda los 4522 bytes y el ciphertext unos 9042 bytes [2], significativamente mayores (en nivel 1, HQC tiene pk ≈ 2,2 KB vs. ∼ 800 B de Kyber512).
En otras palabras, HQC paga un coste en tamaño: sus claves públicas y textos cifrados pueden ser del orden de 3–4 veces más grandes que los de Kyber para lograr seguridad similar.
Asimismo, las operaciones de cifrado en HQC son más lentas (involucran manipular polinomios de longitud miles de bits y decodificar códigos), aunque permanecen en rangos manejables; según evaluaciones, la velocidad de encapsulación de HQC es aproximadamente la mitad de la de BIKE [3], y comparado con Kyber, HQC también resulta más lento, pero suficiente para muchos usos prácticos (en implementaciones optimizadas, las operaciones pueden tomar del orden de microsegundos a pocos milisegundos) [7].
Seguridad y robustez teórica
Donde HQC brilla es en seguridad y robustez teórica; su análisis se considera muy maduro y sólido [7, 3]. NIST evaluó que HQC presentaba ventajas sobre otros candidatos basados en códigos: por ejemplo, BIKE compartía fundamentos similares, pero su análisis de DFR era menos completo, generando incertidumbre [3], y Classic McEliece, si bien extremadamente seguro, carga con claves públicas del orden de cientos de kilobytes a megabytes [1], lo que limita su adopción práctica en muchos entornos.
De hecho, NIST señaló que McEliece podría estandarizarse por la ISO por separado, evitando duplicar esfuerzos [5]. HQC, con su enfoque intermedio, logra un compromiso equilibrado entre tamaño y rendimiento: gracias a la estructura quasi-cíclica, sus parámetros son relativamente manejables (claves y cifrados mucho más pequeños que McEliece, solo modestamente mayores que Kyber) y sus algoritmos suficientemente eficientes, especialmente con optimizaciones de hardware por su naturaleza lineal y bit-paralela [7].
En términos de ventajas y desventajas relativas frente a Kyber y otros estándares PQC:
Diversidad criptográfica: La mayor ventaja de HQC es aportar diversificación en las suposiciones matemáticas. Kyber (ML-KEM) se basa en retículos algebraicos; si mañana se encontrara un ataque cuántico específico contra retículos, todas las implementaciones basadas en ellos estarían en riesgo. HQC, al basarse en códigos, permanecería seguro ante ese hipotético vector de ataque, ofreciendo una segunda línea de defensa y mejorando la cripto-agilidad del ecosistema [5].
Solidez comprobada: Los problemas de decodificación de códigos llevan décadas investigándose. No se conocen algoritmos cuánticos eficientes que los resuelvan significativamente más rápido que los clásicos (a diferencia de la factorización o del logaritmo discreto resueltos por Shor). HQC aprovecha esta solidez histórica y, al no ocultar trampas en su diseño, facilita el análisis formal y la confianza en su resistencia [2, 7].
Tamaño de clave y rendimiento: La principal desventaja de HQC respecto a Kyber es su eficiencia en ancho de banda y tiempo de cómputo. Kyber requiere menos ancho de banda (claves y ciphertext más pequeños) y es muy rápido gracias a la aritmética de polinomios con FFT [6]. HQC, aunque optimizado, maneja vectores de varios kilobytes (p.ej. 10–12KB por transacción frente a 2KB de Kyber), y las operaciones de decodificación pueden ser más costosas [2]. No obstante, estos tamaños y tiempos siguen siendo manejables en la mayoría de aplicaciones.
Fiabilidad y manejo de errores: Kyber es prácticamente determinístico y no presenta fallos de desenlace. HQC, al involucrar decodificación probabilística, introduce un DFR (Decryption Failure Rate), pero este se ha reducido a niveles insignificantes (<10−38 en parámetros estándar), haciendo a HQC tan fiable como Kyber para usos normales [4].
Conclusión
La estandarización de HQC por parte del NIST marca un paso significativo en la búsqueda de una criptografía robusta para la era cuántica. HQC, como representante moderno de la criptografía basada en códigos, demuestra que estos antiguos principios (corrección de errores y decodificación difícil) siguen siendo relevantes y efectivos frente a las amenazas más avanzadas.
Con una construcción ingeniosa que combina códigos clásicos con técnicas de enmascaramiento de errores, HQC logra un balance entre seguridad y eficiencia, reduciendo las brechas que históricamente separaban a los esquemas de códigos de sus contrapartes de retículos.
En el panorama post-cuántico, HQC aporta diversidad matemática y confianza: su hipótesis de seguridad se apoya en problemas que han resistido el embate de investigadores por décadas [3]. Al unirse como estándar alternativo junto a Kyber, refuerza el mensaje de que ninguna sola construcción matemática es infalible, pero con múltiples enfoques podemos asegurar nuestros sistemas criptográficos contra lo desconocido [4].
Las organizaciones y desarrolladores podrán implementar HQC para aumentar la resiliencia de sus comunicaciones; por ejemplo, en infraestructuras críticas o sistemas a largo plazo donde se desee una capa adicional de seguridad en caso de futuros avances criptanalíticos.
HQC también revitaliza el interés en la criptografía basada en códigos, un campo con un linaje largo pero a menudo opacado por otras técnicas. Su éxito en la competición NIST – imponiéndose sobre candidatos como BIKE y Classic McEliece – nos enseña que con ingenio es posible mitigar las limitaciones clásicas (como tamaños de clave) y lograr estándares prácticos basados en códigos.
Aún quedan retos, desde optimizar implementaciones hasta gestionar las patentes asociadas (que, según se informó, estarán licenciadas libre de regalías para facilitar la adopción) [5].
En definitiva, HQC se perfila como un componente esencial en la caja de herramientas criptográficas post-cuánticas. Con su adopción, entramos en una nueva etapa donde los esquemas de cifrado de dos escuelas distintas (retículos y códigos) convivirán para proteger la información. Esta dualidad incrementa la confianza en que nuestros datos permanecerán seguros incluso ante el eventual auge de la computación cuántica.
Como siempre en criptografía, la prudencia aconseja no “poner todos los huevos en la misma canasta matemática” HQC nos ofrece precisamente esa canasta alternativa, cimentada en la corrección de errores y la dificultad de la decodificación, lista para mantener nuestros secretos a salvo en el futuro poscuántico [3].
Desde Cyte, invitamos a la comunidad a explorar e integrar estas nuevas herramientas de criptografía post-cuántica como parte de sus estrategias de seguridad, garantizando así
una transición fiable hacia un mundo resistente al poder de la computación cuántica.
Fuentes
[1] Wikipedia, “McEliece cryptosystem,” https://en.wikipedia.org/wiki/McEliece_cryptosystem.
[2] “Especificación de HQC (2025),” PQC-HQC.org, https://pqc-hqc.org.
[3] Redacción Watchdata, “Cuarta ronda del PQC del NIST: ¡HQC seleccionado como nuevo candidato al KEM!,” https: //www.watchdata.com/es/1007/.
[4] NIST, “NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption (news release),” 2025, https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption.
[5] NIST, “NIST PQC Standardization Process: Fourth Round Status Report (IR 8545),” 2025. https://csrc.nist.gov/pubs/ir/8545 /final
[6] Wikipedia, “Kyber (cryptography),” https://en.wikipedia.org/wiki/Kyber.
[7] PQShield, “FIPS 203 – Module-Lattice KEM (ML-KEM),” 2024, https://csrc.nist.gov/pubs/fips/203/final.
[8] N. Sendrier, “Decoding One Out of Many (DOOM),” in PQCrypto 2011, PKI Consortium, 2011. https://www.researchgate .net/publication/220961279_Decoding_One_Out_of_Many
Si deseas tener siempre a la mano el artículo escrito por José Darío Flórez, te invitamos a descargarlo, compartirlo y comentarnos qué opinas al respecto.
Comments