오류가 있는 학습(LWE)의 기반

Regev(2005)가 제안한 Learning With Errors (LWE)는 Z_q 위에서 여러 개의 잡음이 있는 선형 방정식이 주어졌을 때 비밀 벡터 s를 찾는 문제입니다. 잡음 e는 작지만 가우스 소거법을 수행하지 못하게 합니다. 잡음이 없으면 연립방정식은 쉽지만, 아주 작은 잡음만 있어도 계산적으로 어려운 문제가 됩니다.

비밀 s ∈ Z_q^n을 사용합니다. 공격자는 a_i ∈ Z_q^n이 무작위이고 b_i = + e_i mod q인 샘플 (a_i, b_i)를 받습니다. e_i는 분포 χ에서 나온 작은 잡음입니다(예: σ = √n인 가우스 분포). 다항식 개수만큼의 샘플이 주어졌을 때 s를 찾는 것이 과제입니다.

잡음이 없으면 b_i = mod q이고, 가우스 소거법으로 O(n^3)에 s를 복구할 수 있습니다. 잡음이 있으면 방정식 하나만 잘못되어도 소거 과정 전체가 손상됩니다. 잡음은 키를 사용하면 복호화할 수 있을 만큼 작지만, 암호 분석을 막을 만큼 충분히 큽니다.

Regev는 양자 환원을 통해 LWE가 최악의 경우의 격자 문제(SIVP, GapSVP)로 환원된다는 것을 증명했습니다. 이는 LWE가 깨지면 여러 어려운 격자 문제가 풀린다는 뜻입니다. 하지만 격자 문제에 대한 양자 알고리즘은 알려져 있지 않습니다. 따라서 LWE는 양자 이후 시대에도 안전합니다.

RLWE는 Z_q^n을 원분 다항식 f에 대한 환 Z_q[x]/(f(x))로 대체합니다. 하나의 RLWE 샘플에 n개의 방정식이 인코딩되므로 훨씬 효율적입니다. RLWE는 Kyber (KEM), Dilithium (서명), 그리고 BFV/BGV/CKKS HE 체계의 기반입니다.

보안은 다음 요소에 따라 달라집니다. n(차원, 일반적으로 512-2048), q(법, 1024-2^60), σ(잡음의 표준편차)입니다. n이 클수록, 그리고 σ/q 비율이 작을수록 문제가 어려워집니다. NIST의 양자 이후 표준은 n=256(모듈 차원)과 k개의 모듈(k=2,3,4)을 사용합니다.

공개 키는 (A, b=As+e)입니다. 비트 m을 암호화하려면 무작위 r을 선택하고 암호문 (u=A^T r, v = b^T r + m*q/2)을 계산합니다. 복호화하면 v - s^T u = e^T r + m*q/2 ≈ m*q/2가 됩니다. 가장 가까운 m으로 반올림합니다. 잡음 e는 암호화 중 암호문이 m을 숨기도록 합니다.

Decision-LWE는 (a, As+e)와 u가 균일한 무작위 값일 때의 (a, u)를 구별하는 문제입니다. LWE의 난이도를 가정하면 두 분포는 계산적으로 구별할 수 없습니다. 이는 의미론적 보안의 기반입니다. 비밀 키가 없는 공격자에게 암호문은 무작위 잡음처럼 보입니다.

가장 잘 알려진 공격은 BKZ (Block Korkine-Zolotarev) 격자 축소입니다. 복잡도는 준지수적이지만 다항식적이지는 않습니다. BKZ-β에는 2^{0.292β}번의 연산이 필요합니다. LWE-512의 경우 BKZ에 대한 보안 수준은 약 128비트입니다. BKZ에 대한 양자 속도 향상은 알려져 있지 않습니다.

Module-LWE(Kyber에서 사용됨)는 랭크 k인 모듈 위의 RLWE입니다. k=2이면 512비트 보안, k=3이면 768비트 보안, k=4이면 1024비트 보안을 제공하는 등 유연성이 있습니다. 보안과 성능은 k에 따라 조정됩니다. NIST는 Kyber(이름이 ML-KEM으로 변경됨)를 PQC 표준으로 선정했습니다.

RSA/ECC의 보안은 정수 인수분해와 이산 로그 문제에 기반하므로 쇼어 알고리즘을 통한 양자 공격에 취약합니다. LWE의 보안은 최악의 경우의 격자 문제에 기반하며, 이를 상대로 알려진 양자 속도 향상은 없습니다. 키 크기는 LWE 키가 약 1 KB이고 RSA-2048은 256바이트입니다. LWE는 더 크지만 양자 컴퓨터에 안전합니다.

많은 샘플이 있어도 LWE를 풀기 어려운 이유는 무엇입니까?

LWE는 잡음이 있는 선형 방정식에서 비밀 s를 찾는 문제이며 양자 컴퓨터로도 어렵습니다. RLWE는 효율성을 위해 다항식 환을 사용합니다. LWE/RLWE는 Kyber, Dilithium 및 HE 체계의 기반입니다. 다음 주제: 정수 연산을 위한 BGV 및 BFV HE 체계입니다.