1. 격자 이론 기초: 주기적인 그리드와 근본적인 난제

양자내성암호(PQC)의 가장 유력한 후보인 ‘격자 기반 암호(Lattice-based Cryptography)’는 다차원 격자(Lattice)라는 수학적 구조에 기반합니다.

‘격자(Lattice)’는 n-차원 실수 벡터공간 R^n에서 정수 계수의 선형 결합으로 형성된 이산적인 점들의 집합입니다. 마치 규칙적이고 주기적인 그리드(Periodic Grid)와 같습니다. 격자는 기저(Basis) 벡터들의 집합 b_1, …, b_n 에 의해 정의되며, 이 기저로 생성되는 기본 평행육면체(Fundamental Parallelepiped)의 부피는 격자의 행렬식(Determinant)과 같습니다.

격자 암호의 안전성을 뒷받침하는 근본적인 난제들은 다음과 같습니다:

• 최단 벡터 문제 (SVP, Shortest Vector Problem): 격자 내에서 0이 아닌 벡터 중 가장 짧은 벡터(최소 거리 lambda_1)를 찾는 문제입니다. 이 문제는 일반적으로 NP-hard로 알려져 있습니다.
• 가장 가까운 벡터 문제 (CVP, Closest Vector Problem): 격자 밖에 있는 임의의 목표 벡터 t가 주어졌을 때, 이 벡터와 가장 가까운 격자 벡터를 찾는 문제입니다. 이 역시 일반적으로 NP-hard입니다.
•  

2. PQC 설계의 핵심: LWE와 SIS 난제

격자 기반 암호는 SVP와 CVP에 직접 기반하기보다는, 실용적인 암호 시스템 설계에 유리한 LWE와 SIS 문제에 기반합니다.

격자 암호의 강력함은 LWE나 SIS 문제를 푸는 것이 사실상 SVP와 CVP를 푸는 것과 같이 어렵다는 ‘환원(Reduction)’에 의해 뒷받침됩니다.

3. 격자 기반 암호의 안전성 분석 방법론

격자 기반 암호의 안전성 수준을 평가한다는 것은, 현재 알려진 최적의 공격 알고리즘을 사용했을 때 해당 암호를 깨는 데 필요한 계산 비용을 추정하는 것을 의미합니다.

3.1. 최적 공격 알고리즘: BKZ

현재 격자 문제에 대한 가장 강력한 공격 알고리즘은 BKZ (Block Korkine-Zolotarev) 알고리즘입니다.

• BKZ는 격자 축소(Lattice Reduction)를 통해 격자 기저를 짧게 만들어, SVP나 CVP의 해를 찾는 데 근접하게 만듭니다.
• BKZ 알고리즘의 복잡도는 ‘블록 사이즈 b’에 지수적으로 의존하며, b가 클수록 공격 시간이 기하급수적으로 늘어납니다.

LWE 및 SIS에 대한 공격은 이들을 특정 격자로 변환한 뒤, BKZ를 이용해 SVP/CVP 형태로 공격하는 Primal 공격 또는 Dual 공격 방식으로 이루어집니다.

3.2. Core-SVP 방법론을 통한 난이도 추정

Core-SVP methodology는 BKZ 기반 공격의 시간 복잡도 중 지수적 성장을 보이는 핵심 부분만을 고려하여 격자 기반 알고리즘의 안전성 하한선을 추정하는 표준화된 방법입니다.

이 방법은 LWE/SIS 문제를 해독하는 데 필요한 최소한의 연산량을 Log_2 값으로 나타내어, NIST 보안 레벨(예: Level 2, 3, 5)과의 비교 기준으로 사용됩니다.

4. NIST 표준 ML-DSA (Dilithium)의 안전성 예시

NIST 표준 전자서명 알고리즘인ML-DSA (Dilithium의 표준 명칭)는 격자 기반 암호의 대표적인 예시입니다. 이 알고리즘의 파라미터별 안전성은 Core-SVP 방법론을 통해 다음과 같이 분석됩니다 (문서 내 분석 자료 기반).

• NIST Level 1은 AES-128과 동등한 고전 보안(128 bits)을 요구하며, Level 5는 AES-256과 동등한 고전 보안(256 bits)을 요구합니다.
• Classical Core-SVP 값은 고전 컴퓨터 기반 공격의 난이도를, Quantum Core-SVP 값은 양자 컴퓨터 기반 공격의 난이도를 Log_2 값으로 추정한 것입니다.

이러한 정밀한 분석은 ML-DSA와 같은 격자 기반 PQC 알고리즘이 다가오는 양자 컴퓨팅 환경에서도 충분한 보안 마진을 확보했음을 객관적으로 입증하는 핵심 근거가 됩니다.