NTRU: História, Design e Segurança

O NTRU foi inventado por Hoffstein, Pipher e Silverman em 1996, tornando-se um dos mais antigos sistemas de chave pública pós-quânticos ainda considerados seguros. Ao contrário do RSA e do ECC, que dependem da dificuldade de problemas da teoria dos números, a segurança do NTRU baseia-se na dificuldade de encontrar vetores curtos em um reticulado específico derivado de anéis de polinômios. O NTRU foi comercializado e implantado em vários produtos de segurança antes que a criptografia pós-quântica se tornasse dominante.

O NTRU opera no anel de polinômios truncado Z[X]/(X^N - 1), em que N é primo. Os polinômios nesse anel têm grau no máximo N-1, e a multiplicação dá a volta, isto é, corresponde a uma convolução. A escolha do anel e a estrutura dos polinômios com coeficientes pequenos são centrais tanto para a eficiência do NTRU quanto para suas propriedades de segurança.

A geração de chaves seleciona dois polinômios pequenos f e g, com coeficientes em {-1, 0, 1}. O polinômio f deve ser invertível tanto módulo p, um primo pequeno, normalmente 3, quanto módulo q, um primo maior, normalmente 2048. A chave pública é h = f_q^{-1} * g mod q, em que f_q é o inverso de f módulo q. A chave privada é o par (f, g).

Para criptografar um polinômio de mensagem m com coeficientes pequenos, o remetente escolhe um polinômio pequeno aleatório de mascaramento r e calcula c = r * h + m mod q. O texto cifrado c é um polinômio no mesmo anel. O r aleatório impede que duas criptografias da mesma mensagem pareçam idênticas, garantindo segurança semântica.

A descriptografia calcula a = f * c mod q, escolhendo coeficientes no intervalo (-q/2, q/2]. Em seguida, a mod p recupera f_p * m mod p, e a multiplicação por fp = f^{-1} mod p fornece m. A estrutura de erro pequeno garante que os coeficientes de f * c sejam suficientemente pequenos para que as operações mod q e mod p interajam corretamente e recuperem a mensagem sem falha causada pelo ruído.

O NTRU moderno possui duas famílias de parâmetros padronizadas: NTRU-HPS, de Hoffstein-Pipher-Silverman, e NTRU-HRSS, de Hulsing-Rijneveld-Schanck-Schwabe. O NTRU-HPS usa polinômios de mensagem ternários, enquanto o NTRU-HRSS usa uma codificação aleatorizada para obter taxas menores de falha na descriptografia. Ambos foram finalistas da terceira rodada do PQC do NIST, com conjuntos de parâmetros destinados a níveis de segurança de 128, 192 e 256 bits.

Não se conhece nenhum ataque em tempo polinomial contra o NTRU com parâmetros adequados. Os melhores ataques reduzem-se à busca de um vetor curto em um reticulado NTRU, que é uma instância do problema SVP aproximado. O reticulado NTRU possui uma estrutura específica, com blocos circulantes, que torna o ataque um pouco mais fácil do que em um reticulado aleatório; por isso, os parâmetros são escolhidos com uma margem de segurança que leva essa estrutura em conta.

O NTRU foi amplamente protegido por patentes da NTRU Cryptosystems Inc., posteriormente Security Innovation. As patentes originais foram depositadas em 1996 e 1998. Essa proteção por patentes dificultou a adoção ampla e as implementações de código aberto durante duas décadas. As patentes centrais do NTRU expiraram por volta de 2017; depois disso, as implementações abertas se multiplicaram e o NTRU entrou na competição de padronização do PQC do NIST.

O NTRU foi finalista da terceira rodada da competição de PQC do NIST, ao lado de Kyber, Classic McEliece e SABER. O NIST acabou escolhendo Kyber, ML-KEM, como o principal padrão de KEM, citando sua análise de segurança mais simples e sua concepção mais clara. O NTRU não foi padronizado, mas continua sendo uma alternativa viável, e sua análise contribuiu para a compreensão da segurança de reticulados.

O NTRUPrime, desenvolvido por Bernstein, Chuengsatiansup, Lange e van Vredendaal, remove deliberadamente a estrutura de anel X^N - 1 e a substitui por X^N - X - 1, um polinômio de grau primo. Isso elimina possíveis fragilidades da estrutura de anel cíclico que alguns criptoanalistas acreditam poder ser exploradas. O NTRUPrime também foi um candidato alternativo do PQC do NIST.

O NTRU é anterior aos esquemas baseados em LWE e não possui uma redução formal da dificuldade do pior caso como a redução de LWE de Regev. No entanto, o NTRU é mais rápido na geração de chaves e possui textos cifrados menores do que muitos esquemas LWE com níveis de segurança equivalentes. A contrapartida é uma fundamentação de segurança menos formal, que depende de décadas de experiência em criptoanálise, em vez de uma prova de redução.

O NTRU é um sistema criptográfico pioneiro baseado em reticulados, fundamentado na aritmética de anéis de polinômios. A geração de chaves usa os polinômios pequenos f e g, com chave pública h = f^{-1}*g mod q. A criptografia usa mascaramento aleatório; a descriptografia explora a estrutura de coeficientes pequenos de f. O NTRU não possui uma redução formal do pior caso, mas resistiu a décadas de criptoanálise. Suas patentes expiraram em 2017, e ele foi finalista da terceira rodada do PQC do NIST.