NTRU: historia, diseño y seguridad

NTRU fue inventado por Hoffstein, Pipher y Silverman en 1996, lo que lo convierte en uno de los sistemas de clave pública poscuánticos más antiguos que aún se consideran seguros. A diferencia de RSA y ECC, que se basan en la dificultad de problemas de teoría de números, la seguridad de NTRU se basa en la dificultad de encontrar vectores cortos en un retículo específico derivado de anillos de polinomios. NTRU se comercializó y se implementó en varios productos de seguridad antes de que la criptografía poscuántica se generalizara.

NTRU opera en el anillo de polinomios truncado Z[X]/(X^N - 1), donde N es primo. Los polinomios de este anillo tienen un grado como máximo N-1 y la multiplicación se realiza de forma circular (convolución). La elección del anillo y la estructura de los polinomios con coeficientes pequeños son fundamentales tanto para la eficiencia de NTRU como para sus propiedades de seguridad.

La generación de claves selecciona dos polinomios pequeños f y g con coeficientes en {-1, 0, 1}. El polinomio f debe ser invertible tanto módulo p (primo pequeño, normalmente 3) como módulo q (primo mayor, normalmente 2048). La clave pública es h = f_q^{-1} * g mod q, donde f_q es la inversa de f módulo q. La clave privada es el par (f, g).

Para cifrar un polinomio de mensaje m con coeficientes pequeños, el remitente elige un polinomio pequeño aleatorio de enmascaramiento r y calcula c = r * h + m mod q. El texto cifrado c es un polinomio del mismo anillo. El valor aleatorio r impide que dos cifrados del mismo mensaje parezcan idénticos, lo que proporciona seguridad semántica.

El descifrado calcula a = f * c mod q, seleccionando los coeficientes en el intervalo (-q/2, q/2]. Después, a mod p recupera f_p * m mod p, y multiplicar por fp = f^{-1} mod p da como resultado m. La estructura del error pequeño garantiza que los coeficientes de f * c sean lo bastante pequeños para que las operaciones mod q y mod p interactúen correctamente y recuperen el mensaje sin fallos por ruido.

NTRU moderno tiene dos familias de parámetros estandarizadas: NTRU-HPS (Hoffstein-Pipher-Silverman) y NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS utiliza polinomios de mensaje ternarios, mientras que NTRU-HRSS utiliza una codificación aleatorizada para obtener mejores tasas de fallo en el descifrado. Ambas fueron finalistas de la tercera ronda de NIST PQC, con conjuntos de parámetros orientados a una seguridad de 128, 192 y 256 bits.

No se conoce ningún ataque en tiempo polinómico contra NTRU parametrizado correctamente. Los mejores ataques se reducen a encontrar un vector corto en un retículo NTRU, lo que constituye una instancia del problema SVP aproximado. El retículo NTRU tiene una estructura específica, con bloques circulantes, que hace que sea ligeramente más fácil atacarlo que un retículo aleatorio; por ello, los parámetros se eligen con un margen de seguridad que tiene en cuenta esta estructura.

NTRU estuvo ampliamente protegido mediante patentes por NTRU Cryptosystems Inc. (posteriormente Security Innovation). Las patentes originales se solicitaron en 1996 y 1998. Esta protección mediante patentes obstaculizó durante dos décadas la adopción generalizada y las implementaciones de código abierto. Las patentes principales de NTRU expiraron alrededor de 2017, después de lo cual proliferaron las implementaciones abiertas y NTRU entró en la competición de estandarización NIST PQC.

NTRU fue finalista de la tercera ronda de la competición NIST PQC junto con Kyber, Classic McEliece y SABER. NIST finalmente eligió Kyber (ML-KEM) como el estándar principal de KEM, citando su análisis de seguridad más sencillo y su diseño más limpio. NTRU no se estandarizó, pero sigue siendo una alternativa viable, y su análisis contribuyó a comprender la seguridad de los retículos.

NTRUPrime, desarrollado por Bernstein, Chuengsatiansup, Lange y van Vredendaal, elimina deliberadamente la estructura de anillo X^N - 1 y la sustituye por X^N - X - 1, un polinomio de grado primo. Esto elimina posibles debilidades derivadas de la estructura de anillo cíclico que algunos criptoanalistas creen que podrían explotarse. NTRUPrime también fue un candidato alternativo de NIST PQC.

NTRU es anterior a los esquemas basados en LWE y no cuenta con una reducción formal de dificultad del peor caso como la reducción de LWE de Regev. Sin embargo, NTRU ofrece una generación de claves más rápida y tamaños de texto cifrado menores que muchos esquemas LWE con niveles de seguridad equivalentes. La contrapartida es una base de seguridad menos formal, que depende de décadas de experiencia criptoanalítica en lugar de una demostración de reducción.

NTRU es un criptosistema pionero basado en retículos que utiliza operaciones aritméticas en anillos de polinomios. La generación de claves utiliza polinomios pequeños f y g, con la clave pública h = f^{-1}*g mod q. El cifrado utiliza un enmascaramiento aleatorio; el descifrado aprovecha la estructura de coeficientes pequeños de f. NTRU no tiene una reducción formal del peor caso, pero ha resistido décadas de criptoanálisis. Sus patentes expiraron en 2017 y fue finalista de la tercera ronda de NIST PQC.