오류가 있는 학습: 어려운 문제

오류가 있는 학습(Learning With Errors, LWE) 문제는 2005년 Oded Regev가 양자 이후 암호의 기반으로 제시했습니다. Z_q 위의 무작위 행렬 A와 b = As + e라는 벡터가 주어졌을 때, 목표는 비밀 벡터 s를 찾는 것입니다. 벡터 e는 이산 가우스 분포에서 추출한 작은 오류이므로, 이 문제는 계산적으로 풀기 어렵습니다.

LWE 문제에서 A는 Z_q 위에서 균일하게 추출한 m x n 무작위 행렬이며, q는 소수 법입니다. 비밀 s는 n차원 벡터이고, e는 각 성분이 좁은 가우스 분포에서 추출된 작은 오류 벡터입니다. A의 구조를 알고 있더라도 공격자가 b와 균일한 무작위 벡터를 구별하는 데에는 도움이 되지 않습니다.

LWE에는 두 가지 표준적인 정식화가 있습니다. 탐색형 LWE는 여러 샘플 (A, b)이 주어졌을 때 비밀 s를 복구하는 문제입니다. 결정형 LWE는 샘플 (A, As + e)와 균일한 무작위 쌍 (A, u)을 구별하는 문제입니다. 두 정식화는 다항식 시간에서 동등하므로, 한 문제를 푸는 알고리즘을 다른 문제를 푸는 알고리즘으로 변환할 수 있습니다.

LWE의 오류 항은 표준편차 sigma로 매개변수화된 정수 위의 이산 가우스 분포에서 추출됩니다. sigma가 작으면 e가 q에 비해 짧아져 b가 As mod q와 거의 같아 보입니다. sigma가 0이면 오류가 없어 가우스 소거법으로 시스템을 풀 수 있으므로, 오류는 문제를 어렵게 만드는 데 필수적입니다.

Regev는 놀라운 환원을 증명했습니다. 평균적인 경우의 LWE 샘플을 푸는 것은 격자에서 최악의 경우에 해당하는 최단 벡터 문제(SVP)를 푸는 것만큼 어렵다는 것입니다. 즉, LWE를 효율적으로 깨뜨릴 수 있다면 모든 격자 문제를 효율적으로 풀 수 있습니다. 최악의 경우의 SVP를 다항식 시간에 푸는 고전 알고리즘이나 양자 알고리즘은 아직 알려져 있지 않습니다.

RSA와 타원 곡선 암호와 달리, 알려진 양자 알고리즘 중 LWE에 대해 지수적인 속도 향상을 제공하는 것은 없습니다. Grover 알고리즘이 제공하는 속도 향상은 최대 이차적이며, 최선의 양자 격자 알고리즘(BKZ의 변형)도 적절하게 선택한 매개변수를 사용하는 LWE를 깨뜨리지 못합니다. 따라서 LWE는 양자 이후 보안을 위한 강력한 기반입니다.

LWE의 보안은 차원 n(비밀 길이), 법 q, 오류 표준편차 sigma라는 세 가지 매개변수에 의해 결정됩니다. n이 클수록, q/sigma 비율이 작을수록 보안성이 높아집니다. 128비트 양자 이후 보안에 일반적으로 사용되는 값은 n = 1024, q 약 12289, sigma 약 3.2입니다. 구체적인 보안성을 평가할 때는 Albrecht 등이 만든 격자 추정 도구를 사용합니다.

짧은 정수 해(Short Integer Solution, SIS) 문제는 서명에 사용되는 관련 격자 난이도 가정입니다. Z_q 위의 무작위 행렬 A가 주어졌을 때, Ax = 0 mod q를 만족하는 짧고 0이 아닌 벡터 x를 찾는 문제입니다. SIS는 격자 분야의 해시 함수와 서명 방식의 기반이며, 암호화와 키 캡슐화를 뒷받침하는 LWE를 보완합니다.

간단한 LWE 암호화 방식은 다음과 같이 작동합니다. 공개 키는 (A, b = As + e)이고 비밀 키는 s입니다. 비트 m을 암호화하기 위해 송신자는 무작위 이진 벡터 r을 사용하여 (u, v) = (A^T r, b^T r + m * floor(q/2))를 계산합니다. 복호화에서는 v - s^T u를 계산한 후 반올림하여 m을 복구합니다. 이 방식은 LWE 가정에 따라 IND-CPA 보안을 달성합니다.

LWE는 기본 암호화를 넘어 다양한 암호 구성 방식을 가능하게 했습니다. 여기에는 완전 동형 암호(FHE), 신원 기반 암호(IBE), 속성 기반 암호(ABE), 키 교환 프로토콜이 포함됩니다. CRYSTALS-Kyber(현재 ML-KEM이며 FIPS 203으로 표준화됨)는 실제 환경에 가장 널리 배포된 LWE 기반 방식입니다.

LWE 기반 암호는 이미 운영 시스템에 도입되고 있습니다. Google과 Cloudflare는 2018년부터 2020년까지 Kyber를 사용한 TLS 실험을 진행했습니다. Chrome과 Firefox는 2024년에 하이브리드 TLS 핸드셰이크에서 ML-KEM-768 지원을 추가했습니다. Signal Protocol은 ML-KEM-1024를 사용하는 양자 이후 계층(PQXDH)을 추가하여 순방향 비밀성을 제공하고, 미래의 양자 컴퓨터에 대해서도 장기간의 메시지 기밀성을 보호합니다.

다음 중 LWE 문제의 난이도 보장을 가장 잘 설명하는 것은 무엇입니까?

LWE는 격자 문제에서 최악의 경우를 대상으로 하는 강력한 환원이 뒷받침하는, 가장 많이 연구된 양자 이후 난이도 가정 중 하나입니다. 세 가지 매개변수(n, q, sigma)가 보안성과 성능 사이의 균형을 결정합니다. LWE는 양자 공격에 내성을 가지며 NIST가 표준화한 방식을 뒷받침합니다. LWE를 이해하는 것은 ML-KEM과 ML-DSA를 비롯한 현대의 모든 격자 기반 암호를 이해하는 출발점입니다.