NTRU: 역사, 설계 및 보안

NTRU는 1996년 Hoffstein, Pipher, Silverman이 발명했으며, 현재까지 안전한 것으로 여겨지는 가장 오래된 양자 이후 공개 키 시스템 중 하나입니다. 수론적 난이도에 의존하는 RSA와 ECC와 달리, NTRU의 보안은 다항식 환에서 유도한 특정 격자에서 짧은 벡터를 찾기 어려운 성질에 기반합니다. NTRU는 양자 이후 암호가 주류가 되기 전에 상용화되어 여러 보안 제품에 배포되었습니다.

NTRU는 절단된 다항식 환 Z[X]/(X^N - 1)에서 작동하며, 여기서 N은 소수입니다. 이 환의 다항식 차수는 최대 N-1이고, 곱셈 결과는 순환하며 합성곱이 이루어집니다. 환의 선택과 작은 계수를 갖는 다항식의 구조는 NTRU의 효율성과 보안 특성 모두에서 핵심적인 역할을 합니다.

키 생성에서는 계수가 {-1, 0, 1}에 속하는 두 개의 작은 다항식 f와 g를 선택합니다. 다항식 f는 p(작은 소수이며 일반적으로 3)와 q(더 큰 소수이며 일반적으로 2048) 모두에 대해 가역이어야 합니다. 공개 키는 h = f_q^{-1} * g mod q이며, 여기서 f_q는 q를 법으로 하는 f의 역원입니다. 비밀 키는 (f, g) 쌍입니다.

작은 계수를 갖는 메시지 다항식 m을 암호화하기 위해 송신자는 무작위로 작은 블라인딩 다항식 r을 선택하고 c = r * h + m mod q를 계산합니다. 암호문 c는 같은 환에 속하는 다항식입니다. 무작위 r은 동일한 메시지를 암호화한 결과가 서로 똑같아 보이는 것을 막아 의미론적 보안을 달성합니다.

복호화에서는 a = f * c mod q를 계산하고, 계수를 (-q/2, q/2] 범위에 오도록 선택합니다. 그런 다음 a mod p를 계산하면 f_p * m mod p가 복구되고, fp = f^{-1} mod p를 곱하면 m을 얻습니다. 작은 오류 구조 덕분에 f * c의 계수가 충분히 작게 유지되므로, mod q와 mod p 연산이 올바르게 상호 작용하여 잡음으로 인한 실패 없이 메시지를 복구할 수 있습니다.

현대적인 NTRU에는 두 가지 표준화된 매개변수 계열이 있습니다. NTRU-HPS(Hoffstein-Pipher-Silverman)와 NTRU-HRSS(Hulsing-Rijneveld-Schanck-Schwabe)입니다. NTRU-HPS는 3값 메시지 다항식을 사용하는 반면, NTRU-HRSS는 더 낮은 복호화 실패율을 위해 무작위화된 인코딩을 사용합니다. 두 방식 모두 NIST PQC 3라운드 최종 후보에 올랐으며, 매개변수 집합은 128비트, 192비트, 256비트 보안을 목표로 합니다.

적절한 매개변수를 사용하는 NTRU에 대한 다항식 시간 공격은 알려져 있지 않습니다. 최선의 공격은 NTRU 격자에서 짧은 벡터를 찾는 문제로 환원되며, 이는 근사 SVP 문제의 한 사례입니다. NTRU 격자에는 특정 구조(순환 블록)가 있어 무작위 격자보다 공격하기가 약간 쉬우므로, 이 구조를 고려한 보안 여유를 확보하도록 매개변수를 선택합니다.

NTRU는 NTRU Cryptosystems Inc.(후에 Security Innovation)에 의해 광범위하게 특허를 받았습니다. 최초 특허는 1996년과 1998년에 출원되었습니다. 이러한 특허 보호는 20년 동안 광범위한 도입과 오픈 소스 구현을 가로막았습니다. NTRU의 핵심 특허는 2017년 무렵 만료되었고, 그 후 공개 구현이 확산되면서 NTRU는 NIST PQC 표준화 경쟁에 참여하게 되었습니다.

NTRU는 Kyber, Classic McEliece, SABER와 함께 NIST PQC 대회의 3라운드 최종 후보였습니다. NIST는 결국 더 단순한 보안 분석과 깔끔한 설계를 이유로 Kyber(ML-KEM)를 주요 KEM 표준으로 선택했습니다. NTRU는 표준으로 채택되지 않았지만 여전히 실용적인 대안이며, NTRU에 대한 분석은 격자 보안을 이해하는 데 기여했습니다.

Bernstein, Chuengsatiansup, Lange, van Vredendaal이 개발한 NTRUPrime은 환 구조 X^N - 1을 의도적으로 제거하고 이를 소수 차수 다항식인 X^N - X - 1로 대체합니다. 이를 통해 일부 암호 분석가가 악용할 수 있다고 보는 순환 환 구조의 잠재적인 약점을 제거합니다. NTRUPrime은 NIST PQC의 대체 후보이기도 했습니다.

NTRU는 LWE 기반 방식보다 먼저 등장했으며 Regev의 LWE 환원과 같은 형식적인 최악의 경우 난이도 환원을 갖고 있지 않습니다. 그러나 NTRU는 동일한 보안 수준을 제공하는 많은 LWE 방식보다 키 생성이 빠르고 암호문 크기가 작습니다. 그 대신 형식적인 보안 기반은 약하며, 환원 증명보다는 수십 년에 걸친 암호 분석 경험에 의존합니다.

NTRU는 다항식 환 연산을 기반으로 하는 선구적인 격자 기반 암호 시스템입니다. 키 생성에서는 작은 다항식 f와 g를 사용하고, 공개 키는 h = f^{-1}*g mod q입니다. 암호화에서는 무작위 블라인딩을 사용하며, 복호화에서는 f의 작은 계수 구조를 활용합니다. NTRU는 형식적인 최악의 경우 환원은 없지만 수십 년에 걸친 암호 분석을 견뎌 왔습니다. 특허는 2017년에 만료되었고 NIST PQC 3라운드 최종 후보에 올랐습니다.