Ring-LWE와 모듈러 격자

표준 LWE는 큰 행렬-벡터 곱을 필요로 하므로 키 크기가 커집니다. 2010년 Lyubashevsky, Peikert, Regev가 소개한 Ring-LWE는 벡터와 행렬을 환 R_q = Z_q[X]/(f(X))의 다항식으로 대체합니다. 이렇게 구조화된 환경에서는 훨씬 더 작은 키와 빠른 연산을 사용할 수 있어, Ring-LWE는 실제 격자 암호의 실용적인 기반이 되었습니다.

Ring-LWE에서 사용하는 다항식 f(X)는 일반적으로 f(X) = X^n + 1이며, 여기서 n은 2의 거듭제곱입니다. 이것은 2n차 원분 다항식입니다. 이 다항식은 Z 위에서 기약이고, 환 R_q가 좋은 대수적 특성을 가지며, 효율적인 곱셈을 위한 수론 변환(NTT)을 사용할 수 있기 때문에 선택됩니다. 원분 환은 깊이 연구되어 왔으며 안전한 것으로 여겨집니다.

링 LWE에서 비밀 s는 R_q의 다항식이며, 표본은 (a, b = a*s + e) 형식을 취합니다. 여기서 a는 균등 무작위 환 원소이고 e는 작은 오류 다항식입니다. 공격자는 이러한 표본을 많이 보고 s를 복구하거나, 표본이 균등 무작위로 생성된 것인지 구별해야 합니다. 이 문제의 어려움은 링 LWE 가정에 근거하며, 이 가정은 아이디얼 격자에서의 최악 경우 문제로부터의 환원을 갖습니다.

링 LWE는 공격자에게 더 어려운 문제이지만, 일반 LWE와는 약간 다른 보안 환원을 따릅니다. 이 환원은 임의의 격자가 아니라 아이디얼 격자에서의 최악 경우 문제(아이디얼 SVP)로부터 이루어집니다. 아이디얼 격자의 추가 구조는 원칙적으로 일반 격자보다 문제를 쉽게 만들 수 있으며, 이는 현재 활발히 연구되는 분야입니다. 이 구조를 활용한 실용적인 공격은 아직 알려져 있지 않습니다.

모듈 LWE(M-LWE)는 하나의 환 원소나 정수로 이루어진 큰 행렬 대신 환 원소로 이루어진 k x k 행렬을 사용하여 LWE와 링 LWE를 모두 일반화합니다. k = 1이면 링 LWE로 환원되고, k가 커질수록 표준 LWE에 가까워집니다. 이 조정 가능한 매개변수 k를 사용하면 보안에 대한 신뢰도와 성능 사이의 균형을 맞출 수 있습니다.

CRYSTALS-Kyber(현재는 ML-KEM, FIPS 203)는 R_q 위의 랭크-k 행렬을 사용하는 모듈 LWE를 기반으로 합니다. 매개변수 k가 보안 수준을 직접 결정합니다. k=2는 128비트 보안(ML-KEM-512)을, k=3은 192비트 보안(ML-KEM-768)을, k=4는 256비트 보안(ML-KEM-1024)을 목표로 합니다. 모듈 구조를 사용하면 k를 변경하여 보안 수준을 조절할 수 있는 단일 코드 기반을 구축할 수 있습니다.

R_q = Z_q[X]/(X^n + 1)에서 다항식 곱셈은 성능의 병목입니다. 수론적 변환(NTT)은 Z_q 위에서 수행하는 이산 푸리에 변환으로, 다항식을 평가 형식으로 변환합니다. 이 형식에서는 곱셈이 각 점에서의 곱셈으로 바뀝니다. NTT를 적용할 수 있도록 q를 선택하면 다항식 곱셈에 걸리는 시간이 O(n^2)에서 O(n log n)으로 줄어듭니다. 이는 ML-KEM과 ML-DSA에서 핵심적인 최적화입니다.

NTT를 사용하려면 q가 q = 1 mod 2n을 만족하는 소수여야 하며, 이를 통해 Z_q에 원시 2n차 단위근이 존재하게 됩니다. n = 256인 ML-KEM에서는 q = 3329가 이 요구 사항을 만족합니다. Z_3329 위의 NTT는 SIMD 명령을 지원하는 최신 하드웨어에서 매우 빠르게 실행되므로, 일반적인 중앙 처리 장치에서도 초당 수천 번의 ML-KEM 연산을 수행할 수 있습니다.

링 LWE와 모듈 LWE는 표준 LWE에 비해 키 크기를 크게 줄입니다. 128비트 보안을 위한 표준 LWE 공개 키의 크기는 약 1 MB일 수 있지만, 링 LWE를 사용하면 약 800바이트로 줄어들고, 모듈 LWE(ML-KEM-768)는 192비트 양자 내성 보안을 제공하면서 1184바이트의 공개 키를 사용합니다. 이러한 작은 크기 덕분에 격자 방식은 TLS와 내장형 시스템에서 실용적으로 사용할 수 있습니다.

일부 암호학자는 원분 환의 추가적인 대수 구조가 일반 LWE에는 적용되지 않는 공격을 가능하게 할 수 있다고 우려합니다. 2024년에 Elias Rokicki와 공동 연구자들은 2n차 원분 다항식을 분석하여 실용적인 악용 방법은 찾지 못했지만, 지속적인 검토가 중요하다는 점을 강조했습니다. NIST PQC 과정에서는 이러한 위험을 고려했으며, 하나의 환 구조에 대한 의존도를 낮추기 위해 부분적으로 모듈 LWE를 선택했습니다.

Kyber 외에도 링 LWE는 NIST가 표준화한 서명 방식인 CRYSTALS-Dilithium(ML-DSA)의 기반이 됩니다. 마이크로소프트의 SEAL 라이브러리는 링 LWE를 통해 동형 암호화를 구현합니다. 구글의 Tink 암호 라이브러리에는 ML-KEM 지원 기능이 포함되어 있습니다. 링 LWE는 놀라울 정도로 짧은 기간에 이론적 구성에서 실제 운영 환경에 배포되는 기술로 발전했으며, 그 배경에는 NIST 표준화 과정이 있었습니다.

표준 LWE에 비해 링 LWE가 갖는 가장 큰 장점은 무엇입니까?

링 LWE는 LWE를 다항식 환 R_q = Z_q[X]/(X^n+1)으로 옮겨 키 크기를 크게 줄이고, NTT 기반의 빠른 산술 연산을 가능하게 합니다. 모듈 LWE는 이를 랭크-k 구조로 일반화하며, ML-KEM(FIPS 203)과 ML-DSA(FIPS 204)의 기반이 됩니다. NTT에 적합한 소수 q = 3329는 효율적인 구현을 가능하게 합니다. 보안은 아이디얼 격자와 모듈 격자에서의 문제를 해결하기 어렵다는 점에 근거합니다.