양자 내성 암호와 Dilithium

Part 1: 왜 PQC인가

1.1 현재 블록체인의 암호 기반

오늘날 이더리움을 포함한 대부분의 블록체인은 secp256k1 타원곡선 위에서 ECDSA(Elliptic Curve Digital Signature Algorithm)로 트랜잭션에 서명합니다. 개인키 $k$에서 공개키 $P$를 유도하는 과정은 타원곡선 위의 스칼라 곱으로 정의됩니다.

여기서 $G$는 secp256k1 곡선의 생성원(generator point)이고, $k$는 256비트 정수인 개인키입니다. 곱셈처럼 보이지만 실제로는 타원곡선의 점을 $k$번 더하는 연산입니다.

이더리움 주소는 다음 과정으로 도출됩니다. 먼저 압축되지 않은 공개키(x, y 좌표 각 32바이트, 총 64바이트)에 Keccak-256 해시를 적용한 뒤, 그 결과(32바이트) 중 마지막 20바이트를 주소로 사용합니다. 평소에 우리가 보는 0x... 주소는 공개키 자체가 아니라 공개키의 해시값이기 때문에, 일상적인 상황에서는 공개키가 직접 노출되지 않습니다.

1.2 왜 위험한가: 공개키 노출

문제는 트랜잭션에 서명하는 순간입니다. ECDSA 서명값과 함께 공개키 $P$가 블록체인에 공개됩니다. 공격자가 $P$를 알게 되면, 아래의 수학적 문제를 풀어 개인키 $k$를 복원하려 시도할 수 있습니다.

이것이 바로 ECDLP(Elliptic Curve Discrete Logarithm Problem, 타원곡선 이산대수 문제)입니다. 공개된 $P$와 $G$로부터 $k$를 역산하는 문제입니다.

고전 컴퓨터의 경우 현재 가장 효율적인 알고리즘은 Pollard's rho 알고리즘으로, 시간 복잡도가 $O(\sqrt{n}) \approx O(2^{128})$입니다. $2^{128}$번의 연산은 현존하는 모든 컴퓨터를 동원해도 우주의 나이를 훨씬 초과하는 시간이 걸리므로 사실상 불가능합니다.

그러나 양자 컴퓨터는 다릅니다. Shor 알고리즘을 사용하면 동일한 문제를 다항식 시간 $O((\log n)^3)$ 안에 풀 수 있습니다. $n$이 아무리 커도 자릿수의 세제곱에 비례하는 연산만으로 해결된다는 의미로, 충분한 큐비트를 가진 양자 컴퓨터가 등장하는 순간 ECDSA 기반의 보안은 완전히 무너집니다.

1.3 Shor 알고리즘이 왜 빠른가

Shor 알고리즘의 핵심 아이디어는 ECDLP를 숨은 부분군 문제(Hidden Subgroup Problem, HSP)로 변환하는 것입니다. 구체적으로는 타원곡선 군 위에서 개인키 $k$가 만들어내는 주기적 구조를 찾아냅니다.

이 주기를 찾는 데 양자 푸리에 변환(Quantum Fourier Transform, QFT)이 사용됩니다. QFT는 고전 이산 푸리에 변환(DFT)과 같은 일을 하지만, 양자 중첩(superposition)을 이용해 모든 가능한 입력에 대한 변환을 동시에 수행합니다. 이를 통해 함수의 주기를 지수적으로 빠르게 찾을 수 있습니다.

주기를 알게 되면 군의 구조로부터 개인키 $k$를 계산해낼 수 있습니다. 이것이 가능한 근본적인 이유는 타원곡선 군이 교환법칙(아벨 군, Abelian group)을 만족하기 때문입니다. $P + Q = Q + P$가 항상 성립하는 덧셈 구조가 QFT를 통한 주기 탐색을 가능하게 합니다.

1.4 2029년 데드라인

양자 컴퓨터가 아직 실용화되지 않았는데 왜 지금 대비해야 할까요? 그 답이 "Harvest Now, Decrypt Later(지금 수집하고 나중에 복호화)" 공격입니다. 악의적인 행위자들은 현재 블록체인의 모든 트랜잭션을 저장해두고, 충분한 성능의 양자 컴퓨터가 등장하는 순간 과거 데이터까지 소급하여 공개키에서 개인키를 추출할 수 있습니다. 블록체인에 기록된 데이터는 삭제되지 않으므로 과거의 모든 공개키 노출 기록이 미래의 공격 대상이 됩니다.

이에 대응하여 NIST는 2024년 PQC(Post-Quantum Cryptography) 표준화를 완료했습니다. 주요 표준은 다음과 같습니다.

• ML-DSA (FIPS 204): 디지털 서명 알고리즘, Dilithium이 표준화된 것
• ML-KEM (FIPS 203): 키 캡슐화 메커니즘, Kyber가 표준화된 것

블록체인의 경우 일반 소프트웨어보다 마이그레이션이 훨씬 어렵습니다. 불변성(immutability)이 블록체인의 핵심 특성이기 때문에, 과거에 기록된 주소나 공개키 정보를 변경할 수 없습니다. 네트워크 전체의 합의가 필요한 하드포크와 사용자들의 자발적인 키 마이그레이션이 동시에 이루어져야 하므로 대규모 조율이 필요합니다.

1.5 PQC가 노리는 것

PQC(Post-Quantum Cryptography, 양자 내성 암호)는 양자 컴퓨터로도 풀기 어려운 수학적 문제를 기반으로 설계된 암호 체계입니다. 단순히 키 길이를 늘리는 방식이 아니라, Shor 알고리즘이나 Grover 알고리즘으로 공격해도 지수 시간이 걸리는 근본적으로 다른 수학을 사용합니다.

• 격자(Lattice) 기반: SVP, CVP 등 격자 문제의 어려움에 기반. Dilithium, Kyber가 여기에 속함
• 해시(Hash) 기반: 암호 해시 함수의 단방향성에만 의존. SPHINCS+가 대표적
• 코드(Code) 기반: 오류 정정 코드에서 노이즈 있는 디코딩 문제의 어려움에 기반

이 중 Dilithium은 격자 기반 서명 방식입니다. Part 2부터는 Dilithium을 이해하기 위한 핵심 수학적 기반인 격자 기하학을 차근차근 배워나갑니다.

Part 2: 격자 기하학 기초

2.1 격자란 무엇인가

격자(Lattice) $\mathcal{L}$는 $n$차원 실수 공간 $\mathbb{R}^n$ 안에 존재하는 특별한 점들의 집합입니다. 기저벡터 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d$가 주어질 때, 이 벡터들의 정수 계수 선형결합으로 만들어지는 모든 점의 집합이 바로 격자입니다.

풀어 쓰면 다음과 같습니다.

이 식은 "기저벡터들을 정수 배 한 뒤 더한 모든 점"의 집합을 나타냅니다. 여기서 절대적으로 중요한 조건이 있습니다. 계수 $x_i$가 반드시 정수여야 한다는 것입니다. $x_i$가 실수라면 그냥 벡터 공간(선형 공간)이 되어버리고, 격자 특유의 "듬성듬성한 점들" 구조가 사라집니다.

2D 평면의 간단한 예를 생각해봅시다.

• 기저벡터: $\mathbf{b}_1 = (1, 0)$, $\mathbf{b}_2 = (0, 1)$
• 격자점: $(0,0)$, $(1,0)$, $(0,1)$, $(1,1)$, $(-1, 2)$, $(3, -2)$, ... (모든 정수 좌표점)
• $(0.5, 0.5)$는 격자점이 아님 — 정수 계수로 표현 불가

2.2 기저의 비유일성

같은 격자를 표현하는 기저는 무수히 많습니다. 아래 두 행렬을 봅시다.

$\mathbf{B}_1$은 표준 기저로, 격자점이 정수 좌표 전체인 단순한 격자를 생성합니다. $\mathbf{B}_2$의 기저벡터는 $(3, 2)$와 $(1, 1)$인데, 이 두 벡터의 정수 선형결합으로도 동일한 정수 좌표 격자 전체를 표현할 수 있습니다. 즉 두 기저는 완전히 같은 격자를 가리킵니다.

암호학적으로 중요한 점은, 같은 격자인데도 어떤 기저를 선택하느냐에 따라 문제의 난이도가 극적으로 달라진다는 것입니다.

2.3 좋은 기저 vs 나쁜 기저

격자의 기저 품질은 암호학에서 매우 중요한 개념입니다.

좋은 기저(Good Basis)란 벡터들이 짧고 서로 거의 직교(수직)하는 기저입니다. 좋은 기저를 가지면 격자의 구조가 직관적으로 파악되어 최단 벡터나 가장 가까운 점을 비교적 쉽게 찾을 수 있습니다.

나쁜 기저(Bad Basis)란 벡터들이 길고 서로 거의 평행한, 매우 기울어진 형태의 기저입니다. 나쁜 기저로는 격자의 진짜 구조가 숨겨져 어느 방향으로 탐색해야 할지 전혀 감을 잡기 어렵습니다.

2.4 핵심 어려움 문제: SVP와 CVP

격자 기반 암호학의 안전성은 다음 두 가지 계산 문제의 어려움에 기반합니다.

SVP(Shortest Vector Problem, 최단 벡터 문제)는 격자에서 가장 짧은 영벡터가 아닌 벡터를 찾는 문제입니다.

CVP(Closest Vector Problem, 최근접 벡터 문제)는 임의의 공간상의 점 $\mathbf{t}$에서 가장 가까운 격자점을 찾는 문제입니다.

두 문제의 관계에서 SVP는 CVP의 특수한 경우로 볼 수 있습니다($\text{SVP} \leq \text{CVP}$). 두 문제 모두 NP-hard로 알려져 있으며, 정확한 답뿐 아니라 "정답에서 몇 퍼센트 이내"처럼 조건을 완화한 근사 버전조차도 — 오차 허용 범위가 충분히 작다면 — 여전히 어렵다는 것이 증명되어 있습니다.

2.5 왜 고차원에서 어려운가

2차원이나 3차원의 격자는 시각적으로 명확히 보이고, 최단 벡터나 가장 가까운 점을 눈으로도 찾을 수 있습니다. 그러나 차원이 높아질수록 문제의 어려움은 급격히 증가합니다. 이 현상을 고차원의 저주(Curse of Dimensionality)라고 부릅니다.

구체적으로는 두 가지 이유입니다. 첫째, 공간의 부피가 차원에 대해 지수적으로 증가하지만 격자점의 밀도는 상대적으로 훨씬 낮아집니다. 광활한 공간에 격자점이 듬성듬성 흩어져 있어 탐색 자체가 불가능에 가까워집니다. 둘째, 나쁜 기저로는 탐색 방향을 전혀 잡을 수 없습니다. 1000차원 공간에서 나쁜 기저가 주어지면 어느 방향으로 움직여야 격자점이 가까워지는지 전혀 알 수 없습니다.

기저를 개선하는 알고리즘도 존재합니다. LLL(Lenstra-Lenstra-Lovász)과 BKZ(Block Korkine-Zolotarev) 알고리즘은 나쁜 기저를 "조금 더 좋은" 기저로 변환할 수 있지만, 완전히 좋은 기저로 만들려면 지수적인 시간이 필요합니다.

Part 3: Plain LWE

3.1 LWE란

LWE(Learning With Errors)는 "오차가 섞인 연립방정식을 풀어라"라는 문제입니다. 세팅은 다음과 같습니다.

• 무작위 행렬 $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$: 공개된 계수 행렬
• 비밀 벡터 $\mathbf{s} \in \mathbb{Z}_q^n$: 우리가 찾고 싶은 정답
• 작은 오차 벡터 $\mathbf{e} \in \mathbb{Z}_q^m$: 일부러 집어넣은 잡음

공격자에게는 $(\mathbf{A}, \mathbf{b})$만 공개되며, $\mathbf{b}$는 다음과 같이 계산됩니다.

오차가 없다면 $\mathbf{b} = \mathbf{A}\mathbf{s}$는 단순한 선형 연립방정식이므로 가우스 소거법으로 $O(n^3)$에 풀립니다. 전혀 어렵지 않습니다. 하지만 작은 오차 $\mathbf{e}$가 더해지는 순간, 지금까지 알려진 어떤 효율적인 알고리즘으로도 풀 수 없습니다. 이 아주 단순한 변화가 암호학적 어려움의 근원입니다.

3.2 LWE와 격자의 연결

LWE가 왜 어려운지를 이해하려면, 이 문제를 격자 위에서 바라보는 시각이 필요합니다.

먼저 $q$-진 격자(q-ary lattice)를 정의합니다. 집합 표기로는 다음과 같습니다.

이를 더 직접적으로 쓰면 다음과 같습니다.

즉, "$\mathbf{A}\mathbf{s} + q\mathbf{k}$ 꼴인 모든 정수 벡터"가 격자의 원소입니다. $q$의 배수($q\mathbf{k}$)를 자유롭게 더하거나 뺄 수 있으므로, 격자에 속하는지 여부는 결국 $\mathbf{A}\mathbf{s}$와 mod $q$에서 같은 나머지를 갖느냐로 결정됩니다.

이 격자의 기저행렬 $\mathbf{B}$는 $\mathbf{A}$와 $q\mathbf{I}_m$을 가로로 붙인 형태입니다.

$\mathbf{A}$가 $m \times n$이고 $q\mathbf{I}_m$이 $m \times m$이므로, $\mathbf{B}$는 $m \times (n+m)$ 행렬입니다. 각 열(column)이 격자의 기저벡터 역할을 합니다. 임의의 정수 벡터 $\mathbf{z} = (\mathbf{s};\, \mathbf{k})$에 대해:

이것이 바로 위에서 말한 "$\mathbf{A}\mathbf{s} + q\mathbf{k}$ 꼴"입니다.

핵심 관찰: $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$이므로, $\mathbf{b}$는 격자점 $\mathbf{A}\mathbf{s}$에서 오차 벡터 $\mathbf{e}$만큼 살짝 벗어난 점입니다. 오차가 작다면 $\mathbf{b}$는 격자점 근처에 있겠지만, 정확히 어느 격자점에 얼마나 가까운지는 알 수 없습니다.

3.3 오차 e의 역할

오차 벡터 $\mathbf{e}$는 단순한 잡음이 아닙니다. LWE 보안의 핵심 장치입니다. 그 크기에 따라 문제의 성격이 완전히 달라집니다.

• $\mathbf{e} = 0$ (오차 없음): 선형대수로 $O(n^3)$에 풀립니다. 암호로서 쓸모없습니다.
• $\mathbf{e}$가 너무 큰 경우: 격자점 구조 자체가 사라져 정보 추출 불가. 역시 쓸모없습니다.
• $\mathbf{e}$가 적당히 작은 경우: $\mathbf{b}$는 격자점 근방에 있지만 어느 방향인지 알 수 없습니다. 이것이 어려움의 핵심입니다.

오차의 분포는 보통 이산 가우시안 분포 또는 작은 값에 균등하게 분포하는 균등 분포에서 샘플링합니다. 중요한 것은 $\|\mathbf{e}\|$이 $q$에 비해 충분히 작아야 한다는 점입니다.

3.4 왜 양자 컴퓨터도 못 푸는가

Shor 알고리즘의 핵심 아이디어는 군의 주기(period)를 찾는 것입니다. RSA와 ECDLP는 모두 내부에 주기적 수학 구조를 가지고 있어 QFT가 적용 가능합니다.

반면 LWE는 주기적 구조가 없습니다. $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$에는 QFT가 탐지할 수 있는 주기나 대칭 구조가 없습니다. 따라서 Shor 알고리즘을 적용할 발판 자체가 없습니다.

Grover 알고리즘은 탐색을 $O(\sqrt{N})$으로 가속하지만, 키 크기를 2배 늘리는 것으로 충분히 상쇄할 수 있습니다. NIST 표준은 이를 고려하여 파라미터를 설계했습니다.

3.5 Plain LWE의 한계

LWE는 수학적으로 강력하지만, 그대로 쓰기엔 실용적 문제가 있습니다.

• 큰 공개키: 행렬 $\mathbf{A}$의 크기는 $m \times n$으로, 공개키 크기가 $O(n^2)$에 달합니다. $n = 1024$이면 공개키에 백만 개 이상의 정수가 필요합니다.
• 느린 연산: 행렬-벡터 곱 $\mathbf{A}\mathbf{s}$는 $O(n^2)$으로, 실용적인 암호 시스템에서 허용하기 어렵습니다.

Part 4: 다항식 링

4.1 정수 나눗셈과 몫 환(Quotient Ring)

우리가 매일 쓰는 정수 나눗셈부터 시작합시다. $17 \div 5$를 계산하면 몫은 3, 나머지는 2입니다: $17 = 5 \cdot 3 + 2$.

이를 체계화한 것이 $\mathbb{Z}/q\mathbb{Z}$(또는 $\mathbb{Z}_q$)입니다. $0$부터 $q-1$까지의 정수들로 이루어진 집합이며, 덧셈과 곱셈은 모두 mod $q$로 계산합니다. 예를 들어 $\mathbb{Z}/5\mathbb{Z} = \{0, 1, 2, 3, 4\}$에서:

• $3 + 4 = 7 \equiv 2 \pmod{5}$
• $3 \times 4 = 12 \equiv 2 \pmod{5}$

이처럼 덧셈과 곱셈이 정의되고, 분배법칙이 성립하는 구조를 수학에서 환(Ring)이라고 부릅니다. $\mathbb{Z}/q\mathbb{Z}$는 환의 가장 단순하고 직관적인 예시입니다.

4.2 다항식 링이란

이제 정수 대신 다항식의 세계로 넘어갑니다. $\mathbb{Z}[x]$는 정수 계수를 가진 다항식 전체의 집합입니다. 여기에 정수에서와 마찬가지로 "나머지 연산"을 도입할 수 있습니다. 정수에서 $17 \div 5$의 나머지가 2이듯, 다항식에서도 어떤 다항식으로 나눈 나머지를 취할 수 있습니다.

다항식 나눗셈 예제

$f(x) = x^2 + 1$로 나누는 경우를 살펴봅시다. 예를 들어 $x^3 + 2x + 5$를 $x^2 + 1$로 나누면:

나머지는 $x + 5$이고, 이 나머지의 차수(1)는 나누는 다항식의 차수(2)보다 작습니다. 따라서 $\mathbb{Z}[x]/(x^2+1)$에서 $x^3 + 2x + 5$와 $x + 5$는 같은 원소입니다.

같은 결과를 더 빠르게 얻는 방법이 있습니다. $x^2 \equiv -1 \pmod{x^2+1}$이므로:

차수가 높은 항이 나올 때마다 $x^2 = -1$을 대입해서 차수를 낮추면 됩니다. 한번 더 높은 차수 예시: $x^4 = (x^2)^2 \equiv (-1)^2 = 1$, $x^5 = x \cdot x^4 \equiv x$.

$\mathbb{Z}[x]/(x^2+1)$ 의 원소와 연산

이 링의 원소는 모두 차수 1 이하인 다항식, 즉 $a_0 + a_1 x$ 꼴입니다.

이제 핵심입니다. 이 아이디어를 그대로 $x^{256}+1$로 확장한 것이 Dilithium의 다항식 링입니다.

이 링의 원소는 차수 255 이하의 다항식입니다.

연산 규칙도 동일합니다. 곱셈 시 차수가 256 이상인 항이 나오면 $x^{256} \equiv -1$을 적용해 접어 넣습니다. 예를 들어 $x^{257} = x \cdot x^{256} \equiv -x$, $x^{258} = x^2 \cdot x^{256} \equiv -x^2$. 계수까지 mod $q$로 제한하면 $\mathbb{Z}_q[x]/(x^{256}+1)$이 되며, 이것이 Dilithium이 실제로 사용하는 링입니다.

4.3 컴퓨터에서의 표현

다항식 링의 원소는 컴퓨터에서 매우 단순하게 표현됩니다. $a_0 + a_1 x + \cdots + a_{255} x^{255}$는 그냥 256개의 정수 배열 [a0, a1, ..., a255]입니다. 덧셈은 $O(n)$, 나이브 곱셈은 $O(n^2)$, NTT를 쓰면 $O(n \log n)$입니다.

앞서 다룬 $\mathbb{Z}[x]/(x^2+1)$을 예시로 배열 표현을 확인해봅시다. 이 링의 원소는 $a_0 + a_1 x$ 꼴이므로 길이 2인 배열 [a0, a1]로 표현됩니다.

a = [3, 2]   # 3 + 2x
b = [1, 4]   # 1 + 4x
# (3+2x) + (1+4x) = 4 + 6x
result = [a[0]+b[0], a[1]+b[1]]  # → [4, 6]

a = [3, 2]   # 3 + 2x
b = [1, 4]   # 1 + 4x
# 일반 곱셈: (3)(1) + (3)(4x) + (2x)(1) + (2x)(4x)
#           = 3 + 12x + 2x + 8x²
# x² ≡ -1 이므로 8x² → -8
# 결과: (3 - 8) + (12 + 2)x = -5 + 14x
raw = [0, 0, 0]                          # 차수 0, 1, 2
raw[0] += a[0]*b[0]                      # 3
raw[1] += a[0]*b[1] + a[1]*b[0]         # 14
raw[2] += a[1]*b[1]                      # 8
# x² ≡ -1 이므로 접기
result = [raw[0] - raw[2], raw[1]]       # → [-5, 14]

# Zq[x]/(x^256 + 1) 에서의 덧셈
def poly_add(a, b, q, n=256):
    return [(a[i] + b[i]) % q for i in range(n)]

# 단순 다항식 곱셈 (O(n^2), NTT 없이)
def poly_mul_naive(a, b, q, n=256):
    result = [0] * (2 * n)
    for i in range(n):
        for j in range(n):
            result[i + j] = (result[i + j] + a[i] * b[j]) % q
    # x^256 ≡ -1 이므로 접기
    for i in range(n, 2 * n):
        result[i - n] = (result[i - n] - result[i]) % q
    return result[:n]

"접기(folding)" 단계가 바로 $x^{256} \equiv -1$ 규칙을 구현한 것입니다. 차수 256 이상의 항들을 부호를 반전시켜 차수 0~255의 위치로 더해줍니다.

4.4 왜 $x^{256}+1$인가: NTT를 위한 설계

$x^{256}+1$이라는 선택은 단순한 편의가 아니라, 빠른 연산을 위한 치밀한 설계입니다.

NTT(Number Theoretic Transform)는 정수 나머지 연산 위에서 동작하는 FFT입니다. 다항식 곱셈을 $O(n^2) \to O(n \log n)$으로 가속하면서 부동소수점 오차도 없습니다.

NTT를 $x^n + 1$ 위에서 쓰려면 모듈러스 $q$가 $q \equiv 1 \pmod{2n}$ 조건을 만족해야 합니다. Dilithium은 $n = 256$, $q = 8{,}380{,}417$을 사용합니다. $8{,}380{,}416 = 512 \times 16{,}368$이므로 $q \equiv 1 \pmod{512}$가 성립합니다. 즉, Dilithium의 파라미터는 NTT가 정확히 적용되도록 역산해서 선택된 값입니다.

4.5 Ring-LWE와 Module-LWE

Plain LWE의 병목은 큰 행렬 $\mathbf{A}$에 있었습니다. 핵심 아이디어는 행렬의 각 원소를 정수 대신 다항식 링의 원소로 교체하는 것입니다.

링 $R_q = \mathbb{Z}_q[x]/(x^{256}+1)$을 정의합니다. 이 링의 원소 하나가 256개의 정수를 패킹하고 있습니다.

• Ring-LWE: $\mathbf{A}$가 스칼라 하나 대신 $R_q$의 원소 하나(다항식 하나). 공개키 크기가 $O(n^2)$에서 $O(n)$으로 급감합니다.
• Module-LWE: $\mathbf{A} \in R_q^{k \times \ell}$ — $k \times \ell$ 크기의 작은 행렬인데 각 원소가 $R_q$의 다항식. 보안 수준을 파라미터 $k, \ell$로 유연하게 조절 가능합니다.

$k \times \ell$ 행렬이지만 원소 하나가 256개 정수를 담고 있으므로, 실질 차원은 $256k \times 256\ell$입니다. Dilithium2의 $4 \times 4$ 다항식 행렬은 실질적으로 $1024 \times 1024$ 정수 행렬과 맞먹습니다.

Dilithium2의 행렬 $\mathbf{A} \in R_q^{4 \times 4}$가 실제로 어떻게 생겼는지 살펴봅시다. 각 원소를 계수 튜플로 직접 펼치면:

각 원소의 (...)는 256개 정수의 나열이며, 이것이 곧 $R_q$ 위의 다항식입니다.

예를 들어 $\mathbf{a}_{00}$을 다항식으로 쓰면:

따라서 실제 담고 있는 정수의 수는:

LWE의 기본 구조는 그대로 유지됩니다.

단, 이제 모든 연산이 다항식 링 $R_q$ 위에서 이루어집니다.

Part 5: Dilithium 구조

Dilithium은 NIST FIPS 204 표준으로 채택된 ML-DSA (Module Lattice-based Digital Signature Algorithm)입니다. Module-LWE 문제의 어려움에 안전성 근거를 두고 있으며, 양자 컴퓨터로도 효율적으로 풀 수 없다고 알려진 격자 기반 서명 알고리즘입니다.

5.1 파라미터

Dilithium은 목표하는 보안 레벨에 따라 세 가지 파라미터 셋을 제공합니다. $(k, \ell)$은 행렬 $\mathbf{A} \in R_q^{k \times \ell}$의 크기를 결정하며, $\eta$는 비밀키 다항식 계수의 범위입니다. 모든 파라미터 셋은 동일한 소수 $q = 8{,}380{,}417$을 공유합니다.

비교를 위해: ECDSA (secp256k1)은 공개키가 33B, 서명이 64B에 불과합니다. Dilithium은 수십 배 크지만, 양자 컴퓨터에 대한 내성을 제공합니다.

$\eta$는 비밀키 다항식의 각 계수가 가질 수 있는 범위입니다. 계수는 $\{-\eta, \ldots, \eta\}$ 내의 정수이므로, 비밀키 공간의 크기는 다음과 같습니다.

Dilithium2에서는 $\eta = 2$, $\ell = 4$이므로 $(5)^{1024}$가지 비밀키 후보가 존재합니다. 전수 탐색은 사실상 불가능합니다.

$\eta$를 굳이 작게 유지하는 이유는 서명 효율성 때문입니다. 서명 과정에서 $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$을 계산할 때, $\mathbf{s}_1$의 계수가 작을수록 $\mathbf{z}$가 "너무 커서 폐기"되는 경우(거부 샘플링 실패)가 줄어들어 평균 서명 시도 횟수가 감소합니다. 계수 범위가 크면 폐기율이 높아져 서명 생성이 느려집니다. 또한 비밀키 계수가 작아야 $\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$에서 $\mathbf{s}_1, \mathbf{s}_2$의 존재를 숨길 수 있어 보안 증명이 성립합니다.

5.2 키 생성 (Key Generation)

Dilithium의 키 생성은 작은 랜덤 씨앗에서 시작하여 결정론적으로 모든 구조를 파생시키는 방식입니다.

1. 씨앗 샘플링: 32바이트 랜덤 씨앗 $\xi$를 균등하게 샘플링합니다.
2. 행렬 생성: $\rho \leftarrow \text{SHAKE-256}(\xi)$를 유도하고, $\rho$를 이용하여 공개 행렬 $\mathbf{A} \in R_q^{k \times \ell}$을 결정론적으로 확장합니다. $\mathbf{A}$ 전체를 저장하지 않고 $\rho$(32바이트)만 저장합니다.
3. 비밀키 샘플링: 두 개의 작은 다항식 벡터를 샘플링합니다. $$\mathbf{s}_1 \in S_\eta^\ell, \quad \mathbf{s}_2 \in S_\eta^k$$
4. $\mathbf{t}$ 계산: $$\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$$ 이 식의 구조가 바로 Module-LWE 문제 인스턴스입니다.
5. 비트 분리: $\mathbf{t}$를 상위 비트 $\mathbf{t}_1$과 하위 비트 $\mathbf{t}_0$으로 분리합니다.
6. 공개키: $pk = (\rho,\; \mathbf{t}_1)$
7. 비밀키: $sk = (\rho,\; K,\; tr,\; \mathbf{s}_1,\; \mathbf{s}_2,\; \mathbf{t}_0)$
   $K$는 서명 시 난수 생성에 사용하는 키이고, $tr = \text{SHAKE-256}(pk)$는 공개키의 해시값입니다.

5.3 서명 (Signing) — 개념 이해 위주

Dilithium의 서명은 Fiat-Shamir with Aborts 패러다임을 따릅니다. 핵심 직관: 서명자가 마스킹 벡터 $\mathbf{y}$를 이용해 비밀키 $\mathbf{s}_1$을 직접 드러내지 않으면서도, 비밀키를 알고 있다는 사실을 증명합니다.

1. 마스킹 벡터 샘플링: $\mathbf{y} \in S_{\gamma_1}^\ell$을 균등하게 샘플링합니다. $\gamma_1$은 비밀키 범위 $\eta$보다 훨씬 큰 값으로, $\mathbf{y}$가 $\mathbf{s}_1$을 통계적으로 가리는 역할을 합니다.
2. $\mathbf{w}$ 계산: $\mathbf{w} = \mathbf{A}\mathbf{y}$
3. 챌린지 해시: $$c = H(\text{HighBits}(\mathbf{w}),\; \mu)$$ $\mu$는 메시지 해시, $c$는 계수가 매우 작은 다항식으로 검증자의 챌린지 역할을 합니다.
4. 응답 계산: $$\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$$
5. 거부 샘플링 (Rejection Sampling): $\mathbf{z}$가 너무 크거나 $\mathbf{w} - c\mathbf{s}_2$가 비밀키 정보를 누출할 위험이 있으면 버리고 처음부터 재시작합니다. 이 "거부" 메커니즘이 비밀키를 보호하는 핵심입니다.
6. 힌트 계산: 검증자가 $\mathbf{w}$의 상위 비트를 복원하는 데 필요한 힌트 벡터 $\mathbf{h}$를 계산합니다.
7. 서명 출력: $\sigma = (\mathbf{z},\; \mathbf{h},\; c)$

5.4 검증 (Verification)

검증자는 공개키 $pk = (\rho, \mathbf{t}_1)$과 서명 $\sigma = (\mathbf{z}, \mathbf{h}, c)$, 메시지로부터 다음을 수행합니다.

1. $\rho$로부터 행렬 $\mathbf{A}$를 결정론적으로 재생성합니다.
2. 힌트 $\mathbf{h}$를 이용해 다음을 계산합니다. $$\mathbf{w}' = \mathbf{A}\mathbf{z} - c\mathbf{t}_1 \cdot 2^d$$
3. 재계산된 $\mathbf{w}'$로부터 챌린지를 다시 유도합니다. $$c' = H(\text{HighBits}(\mathbf{w}'),\; \mu)$$
4. 다음 두 조건이 모두 만족되면 유효한 서명입니다.
   • $c = c'$ (챌린지 일치)
   • $\|\mathbf{z}\|_\infty < \gamma_1 - \beta$ (응답 벡터 크기 허용 범위 이내)

Part 6: 실용 적용

6.1 키/서명 크기 비교

ECDSA 대비 Dilithium2 기준으로 공개키는 약 40배, 서명은 약 38배 커집니다. 블록체인 트랜잭션 크기와 네트워크 대역폭, 온체인 저장 비용에 직접적인 영향을 미칩니다.

6.2 블록체인 통합 과제

Ethereum (EVM) 호환성 문제:

• EVM의 ecrecover 프리컴파일이 ECDSA를 전제로 하드코딩되어 있습니다. 서명에서 공개키를 복원하는 방식 자체가 secp256k1 수학에 의존합니다.
• Dilithium은 구조적으로 서명에서 공개키를 복원할 수 없습니다. 공개키를 트랜잭션에 명시적으로 포함해야 합니다.
• EVM 위에서 Dilithium 검증 로직을 순수 Solidity로 구현하면 gas 비용이 매우 높아집니다. 프리컴파일 추가 없이는 현실적인 사용이 어렵습니다.

Cosmos SDK의 유연성:

Cosmos SDK는 처음부터 crypto-agnostic하게 설계되어 있습니다. 암호 알고리즘이 아래 두 인터페이스만 구현하면 어떤 알고리즘이든 교체해서 끼울 수 있습니다.

// 이 인터페이스만 구현하면 어떤 알고리즘이든 끼울 수 있음
type PrivKey interface {
    Sign(msg []byte) ([]byte, error)
    PubKey() PubKey
    Bytes() []byte
}

type PubKey interface {
    VerifySignature(msg []byte, sig []byte) bool
    Bytes() []byte
    Address() Address
}

secp256k1, ed25519 모두 이 인터페이스의 구현체일 뿐입니다. Dilithium 구현체를 만들어서 끼우면 기존 SDK 코드는 그대로 동작합니다. Ethereum처럼 프로토콜 레벨 하드포크 없이, 인터페이스 구현 문제로 국한된다는 점이 핵심입니다.

• DoraFactory의 pqc-cosmos 프로젝트는 Dilithium을 CometBFT에 통합한 실제 사례입니다.
• 주소 도출: $\text{SHA-256}(\text{pubkey}) \rightarrow \text{RIPEMD-160} \rightarrow \text{bech32 인코딩}$ (기존 Cosmos 방식 그대로 — Dilithium 공개키 ~1.3KB도 해시 후 20바이트)

6.3 Dilithium 기반 주소 생성

Ethereum 스타일로 Dilithium 공개키에서 주소를 도출한다면, 해시 함수만 그대로 적용하면 됩니다. 공개키가 1,312바이트로 커졌더라도 해시 출력은 항상 고정 크기이기 때문입니다.

from dilithium_py.dilithium import Dilithium2
from Crypto.Hash import keccak

# 키 생성
pk, sk = Dilithium2.keygen()

# Ethereum 스타일 주소 도출
k = keccak.new(digest_bits=256)
k.update(pk)
address = "0x" + k.hexdigest()[-40:]

print(f"공개키 크기: {len(pk)} bytes")  # 1312 bytes
print(f"주소: {address}")               # 여전히 20 bytes (160 bits)

6.4 번외: "키공간이 커지면 주소 충돌도 늘어나지 않나?"

결론부터: 충돌 확률은 공개키 공간의 크기와 무관하며, 오직 해시 출력 크기에만 의존합니다.

주소는 Hash(공개키) → 20 bytes로 만들어집니다. 공개키가 33B든 1312B든, 해시 출력이 160비트이면 가능한 주소의 수는 $2^{160}$으로 동일합니다. 충돌 확률은 해시 함수의 출력 크기가 결정합니다:

• 160비트 해시 출력 → $2^{160}$가지 가능한 주소
• 현재 전세계 이더리움 활성 주소: 약 $10^9$개
• 새 주소가 기존 주소와 충돌할 확률: $\approx \dfrac{10^9}{2^{160}} \approx 10^{-39}$

감각적으로는: 우주의 원자 수가 약 $10^{80}$개인데, 이 확률은 눈 감고 임의로 원자 하나를 집었을 때 특정 원자가 나올 확률보다 $10^{41}$배 더 작습니다. ECDSA든 ML-DSA든 이 숫자는 동일합니다.

오히려 수학적으로 흥미로운 사실은, 비둘기집 원리에 의해 하나의 주소에 평균 $2^{4755-160} = 2^{4595}$개의 ML-DSA 공개키가 매핑됩니다. 하지만 그 중 하나를 찾아내는 것은 해시 역상(preimage) 공격이고, 여전히 $2^{160}$의 연산이 필요합니다. 정답이 많아도 탐색 비용은 줄지 않습니다.

Grover 알고리즘(양자): 해시 역상 공격을 $O(2^{80})$으로 줄일 수 있어 주소 길이 자체를 32바이트로 늘리자는 논의가 일부 PQC 설계에서 존재합니다. 서명을 ML-DSA로 교체해도 주소 체계는 별도 검토가 필요한 이유입니다.

6.5 dilithium-py 실습

Python 환경에서 ML-DSA 서명을 직접 실험할 수 있습니다. 키 구조 파싱, Ethereum/Cosmos 주소 도출, 위조 감지, 파라미터별 크기 비교까지 한 번에 확인합니다.

pip install dilithium-py pycryptodome

import hashlib
from Crypto.Hash import keccak
from dilithium_py.ml_dsa import ML_DSA_44, ML_DSA_65, ML_DSA_87


def ethereum_address(pk: bytes) -> str:
    """Keccak256(pubkey)의 마지막 20 bytes → 0x... (42자)"""
    k = keccak.new(digest_bits=256)
    k.update(pk)
    return "0x" + k.hexdigest()[-40:]


def cosmos_address(pk: bytes, prefix: str = "cosmos") -> str:
    """SHA256(pubkey) → RIPEMD160 → bech32 인코딩"""
    sha = hashlib.sha256(pk).digest()
    ripe = hashlib.new("ripemd160", sha).digest()
    return bech32_encode(prefix, bech32_convert(ripe, 8, 5))


# bech32 인코딩 (RFC 표준)
_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"

def bech32_polymod(values):
    gen = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
    chk = 1
    for v in values:
        top = chk >> 25
        chk = (chk & 0x1ffffff) << 5 ^ v
        for i in range(5):
            chk ^= gen[i] if ((top >> i) & 1) else 0
    return chk

def bech32_encode(hrp: str, data: list) -> str:
    combined = data + [0, 0, 0, 0, 0, 0]
    polymod = bech32_polymod([ord(c) >> 5 for c in hrp] + [0] +
                              [ord(c) & 31 for c in hrp] + combined) ^ 1
    checksum = [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]
    return hrp + "1" + "".join(_CHARSET[d] for d in data + checksum)

def bech32_convert(data: bytes, from_bits: int, to_bits: int) -> list:
    acc, bits, result = 0, 0, []
    max_v = (1 << to_bits) - 1
    for b in data:
        acc = ((acc << from_bits) | b) & 0xFFFFFFFF
        bits += from_bits
        while bits >= to_bits:
            bits -= to_bits
            result.append((acc >> bits) & max_v)
    return result


def parse_public_key(pk: bytes) -> dict:
    return {
        "rho (A 시드)":   pk[:32],
        "t1  (A·s1+s2)": pk[32:],
    }

def parse_secret_key(sk: bytes) -> dict:
    return {
        "rho (A 시드)":    sk[:32],
        "K   (서명 시드)": sk[32:64],
        "tr  (pk 해시)":   sk[64:128],
        "s1  (비밀 벡터)": sk[128:512],
        "s2  (비밀 벡터)": sk[512:896],
        "t0  (t 하위비트)":sk[896:],
    }

def demo(name, scheme):
    print(f"\n{'='*60}")
    print(f"  {name}")
    print(f"{'='*60}")

    pk, sk = scheme.keygen()
    print(f"\n[키 크기]")
    print(f"  공개키: {len(pk):>5} bytes")
    print(f"  비밀키: {len(sk):>5} bytes")

    print(f"\n[공개키 구조]")
    for label, value in parse_public_key(pk).items():
        print(f"  {label}: {len(value):>5} bytes  {value.hex()[:32]}...")

    # 비밀키 구조는 ML-DSA-44만 출력
    if name == "ML-DSA-44 (Dilithium2)":
        print(f"\n[비밀키 구조]")
        for label, value in parse_secret_key(sk).items():
            print(f"  {label}: {len(value):>5} bytes  {value.hex()[:32]}...")

    eth_addr = ethereum_address(pk)
    cos_addr = cosmos_address(pk)
    print(f"\n[지갑 주소]")
    print(f"  Ethereum (Keccak256[-20B]): {eth_addr}")
    print(f"  Cosmos   (SHA256→RIPE160):  {cos_addr}")

    msg = b"Hello, post-quantum world!"
    sig = scheme.sign(sk, msg)
    valid = scheme.verify(pk, msg, sig)

    print(f"\n[서명]")
    print(f"  서명 크기: {len(sig)} bytes")
    print(f"  서명 (앞 32B): {sig.hex()[:64]}...")
    print(f"  검증 결과: {'OK' if valid else 'FAIL'}")

    # 위조 서명 감지
    tampered = bytearray(sig)
    tampered[0] ^= 0xFF
    invalid = scheme.verify(pk, msg, bytes(tampered))
    print(f"  위조 서명 검증: {'OK (버그!)' if invalid else 'FAIL (정상)'}")


if __name__ == "__main__":
    print("\nCRYSTALS-Dilithium / ML-DSA 데모")
    print("NIST FIPS 204 표준 (2024)")

    demo("ML-DSA-44 (Dilithium2)", ML_DSA_44)  # NIST Level 2, ~128bit
    demo("ML-DSA-65 (Dilithium3)", ML_DSA_65)  # NIST Level 3, ~192bit
    demo("ML-DSA-87 (Dilithium5)", ML_DSA_87)  # NIST Level 5, ~256bit

    print(f"\n{'='*60}")
    print("  ECDSA 대비 요약")
    print(f"{'='*60}")
    print(f"  {'':20} {'ECDSA':>10} {'ML-DSA-44':>10} {'ML-DSA-65':>10} {'ML-DSA-87':>10}")
    print(f"  {'공개키':20} {'33B':>10} {'1312B':>10} {'1952B':>10} {'2592B':>10}")
    print(f"  {'비밀키':20} {'32B':>10} {'2528B':>10} {'4000B':>10} {'4864B':>10}")
    print(f"  {'서명':20} {'64B':>10} {'2420B':>10} {'3309B':>10} {'4627B':>10}")
    print(f"  {'보안 레벨':20} {'128bit':>10} {'128bit':>10} {'192bit':>10} {'256bit':>10}")
    print(f"  {'양자 안전':20} {'X':>10} {'O':>10} {'O':>10} {'O':>10}")