3단계: 미래 암호학의 최전선 — 격자, 영지식, 그리고 비밀의 연산

1부. 이론적 기초 — 왜 지금, 왜 이것인가?

위기의 서막: 1994년에 한 수학자가 세계를 흔들었다

2단계에서 우리는 RSA와 ECC가 왜 안전한지 배웠다. RSA는 거대한 수의 소인수분해가 어렵다는 사실에, ECC는 타원곡선 위의 이산 로그 문제가 어렵다는 사실에 기댄다. 그 "어렵다"는 것의 의미는 구체적으로, 현재의 고전 컴퓨터로는 수십억 년이 걸린다는 뜻이다. 그런데 여기에 치명적인 가정이 숨어 있다. "고전 컴퓨터로는" 이라는 단서 말이다.

1994년, MIT의 수학자 피터 쇼어(Peter Shor)는 양자 컴퓨터가 있다면 RSA와 ECC를 다항 시간(polynomial time) 에 — 즉, 현실적인 시간 안에 — 깨버릴 수 있는 알고리즘을 발표했다. 이것이 쇼어 알고리즘(Shor's Algorithm) 이다. 2단계에서 배운 모든 공개키 암호가 이론적으로는 이미 박살 난 셈이다. 1996년에는 로브 그로버(Lov Grover)가 양자 컴퓨터로 대칭키 암호의 보안 강도를 절반으로 줄이는 그로버 알고리즘(Grover's Algorithm) 을 발표했다. AES-128은 사실상 64비트 수준의 보안이 되어버리는 것이다.

"그래서 양자 컴퓨터가 실제로 있어?" 라고 물을 수 있다. IBM은 2023년에 1,000큐비트 이상의 양자 프로세서를 발표했다. 현재 RSA-2048을 깨려면 수백만 개의 논리 큐비트(logical qubit) 가 필요하고, 오류 수정까지 고려하면 아직 멀었다. 하지만 "Harvest Now, Decrypt Later(지금 수집하고 나중에 해독하자)" 전략이 이미 시작되었다는 점이 핵심이다. 지금 암호화된 외교 통신, 의료 기록, 금융 데이터를 적들이 저장해두고, 양자 컴퓨터가 완성되는 날 일괄 해독하려는 시나리오다. NIST(미국 국립표준기술연구소) 는 이 위협을 심각하게 받아들여 2016년부터 포스트 양자 암호 표준화 공모를 시작했고, 2024년 8월에 마침내 첫 번째 표준을 발표했다.

[노트 기록] 쇼어 알고리즘: 정수 인수분해 & 이산 로그를 양자 컴퓨터로 O(log³ N) 에 해결 → RSA, ECC 붕괴. 그로버 알고리즘: 비정렬 데이터에서 O(√N) 탐색 → 대칭키 보안 절반 감소.

새로운 수학의 무대: 격자(Lattice)란 무엇인가?

이제 우리는 새로운 수학적 세계로 들어간다. 격자(lattice) 는 한 마디로 "고차원 공간 위의 규칙적인 점들의 배열"이다. 2차원으로 생각해보면 바둑판의 교차점들이 하나의 격자다. 하지만 암호학에서는 이걸 수백 차원으로 확장한다.

수학적으로, n차원 격자 $L (B)$ 는 선형 독립인 벡터들의 집합 $B = {b_{1}, b_{2}, \dots, b_{n}}$ (이것을 기저(basis) 라 부른다)의 정수 선형 결합(integer linear combination) 으로 이루어진 모든 점의 집합이다.

$L (B) = {i = 1 \sum n a_{i} b_{i} : a_{i} \in Z}$

여기서 핵심적인 사실이 하나 있다. 같은 격자를 표현하는 기저는 무수히 많다는 것이다. 좋은 기저(거의 직교하는 짧은 벡터들)는 격자를 탐색하기 쉽게 만들고, 나쁜 기저(심하게 기울어진 긴 벡터들)는 탐색을 극도로 어렵게 만든다. 이 비대칭성에서 암호학적 힘이 나온다.

격자 기반 암호학에는 두 가지 핵심 난제가 있다. 첫째는 SVP(Shortest Vector Problem, 최단 벡터 문제): 격자에서 영벡터가 아닌 가장 짧은 벡터를 찾아라. 둘째는 CVP(Closest Vector Problem, 최근접 벡터 문제): 주어진 임의의 점에서 가장 가까운 격자점을 찾아라. 수학자들은 50년 이상 이 문제들을 연구했고, 양자 컴퓨터조차 이 문제들을 다항 시간 안에 풀지 못한다는 것이 현재의 지배적인 견해다. (Ajtai, 1996; Regev, 2005)

잠깐, 스스로 생각해보자. 2단계에서 RSA는 "소인수분해가 어렵다"는 단 하나의 수학적 가정에 기댔다. 만약 그 가정이 틀리면? 격자 기반 암호는 어떤 가정에 기대는가? 그리고 그 가정이 왜 양자 컴퓨터에도 안전한가?

[노트 기록] 격자의 정의: $L (B) = {\sum a_{i} b_{i} : a_{i} \in Z}$ . SVP: 가장 짧은 격자벡터 찾기. CVP: 임의 점에서 가장 가까운 격자점 찾기. 두 문제 모두 NP-hard이며 양자 알고리즘도 지수적 시간 필요.

두 번째 배경: 증명이란 무엇인가?

영지식 증명으로 가기 전에, 우리는 "증명"의 본질에 대해 생각해야 한다. 수학에서 증명이란 어떤 명제가 참임을 납득시키는 논리적 절차다. 그런데 여기에 뒤틀린 질문을 던져보자. 내가 어떤 것을 알고 있다는 사실을 증명하되, 내가 아는 것의 내용은 단 1비트도 드러내지 않을 수 있을까?

상식적으로는 불가능할 것 같다. 뭔가를 증명하려면 증거를 보여줘야 하지 않나? 하지만 1985년 MIT의 샤피 골드와서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali), 찰스 라코프(Charles Rackoff)는 이것이 가능하다는 것을 수학적으로 증명했다. 이들의 논문 "The Knowledge Complexity of Interactive Proof Systems"는 계산 복잡도 이론의 역사를 바꿨고, 이 세 사람은 2012년 튜링상을 받았다.

직관적인 예시로 시작하자. 내가 색맹인 친구 빅터(Victor)에게, 내가 두 공의 색깔을 구분할 수 있다는 것을 증명하고 싶다. 빅터는 빨간 공과 초록 공을 들고 있다. 나는 색맹이 아니어서 구분한다. 빅터가 등 뒤에서 공을 섞거나 섞지 않은 뒤 "내가 공을 바꿨나?"라고 묻는다. 내가 매번 정확히 답한다면, 충분히 많은 반복 후에 빅터는 내가 정말로 색을 구분할 수 있다고 확신할 것이다. 그런데 빅터는 내가 어떻게 색깔을 구분하는지, 즉 색깔 자체에 대한 정보는 아무것도 얻지 못했다. 이것이 영지식 증명의 직관이다.

[노트 기록] ZKP의 세 조건: ① 완전성(Completeness): 참인 명제는 항상 증명 가능. ② 건전성(Soundness): 거짓 명제는 확률적으로도 증명 불가. ③ 영지식성(Zero-Knowledge): 증명자가 알고 있는 비밀에 대해 검증자는 아무것도 새로 배우지 못함.

세 번째 배경: 비밀을 나누면서도 지키는 법

세 번째 배경지식은 비밀 공유(secret sharing) 다. 회사의 핵심 암호가 있는데, 단 한 명이 갖고 있다가 죽어버리면 암호가 사라진다. 그렇다고 여러 명에게 그냥 복사본을 주면 보안이 약해진다. 이 딜레마를 어떻게 풀까?

1979년, 아디 샤미르(Adi Shamir — RSA의 'S'다!)는 샤미르 비밀 공유(Shamir's Secret Sharing) 를 발명했다. 핵심 아이디어는 초등학교 때 배운 것에서 나온다. 두 점이 있으면 직선(1차 함수)이 유일하게 결정된다. 세 점이 있으면 포물선(2차 함수)이 유일하게 결정된다. 이 기하학적 사실을 암호학에 쓰는 것이다.

비밀을 $s$ 라 하자. $k$ 명이 모여야 비밀을 복원할 수 있도록 하려면, 다음 다항식을 구성한다: $f (x) = s + a_{1} x + a_{2} x^{2} + \dots + a_{k - 1} x^{k - 1} (mod p)$ . 여기서 $a_{1}, \dots, a_{k - 1}$ 는 무작위로 선택된 계수다. 비밀 $s = f (0)$ 이다. 각 참가자는 $(i, f (i))$ 라는 조각을 받는다. $k$ 명이 모이면 라그랑주 보간법(Lagrange interpolation)으로 다항식을 복원하고, $f (0)$ 을 계산해 비밀을 얻는다. $k - 1$ 명이 모여도 $f (0)$ 에 대한 정보는 수학적으로 0이다. (단, $p$ 가 충분히 큰 소수인 경우)

스스로 생각해보자. 이 아이디어를 확장하면 어떻게 될까? 각 참가자가 자기 비밀 조각을 드러내지 않으면서, 공통으로 어떤 계산을 수행할 수 있을까? 이것이 다자간 연산(MPC)의 핵심 질문이다.

2부. 본 내용 — 세 가지 혁명적 프로토콜

I. 격자 기반 포스트 양자 암호: LWE와 CRYSTALS-Kyber

배경에서 격자의 어려움을 이해했다면, 이제 그것을 어떻게 암호로 만드는지 보자. 2005년 오데드 레게브(Oded Regev)가 발표한 LWE(Learning With Errors, 오류 학습 문제) 가 현대 격자 암호의 심장이다. (Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography", STOC 2005)

LWE의 설정은 다음과 같다. 비밀 벡터 $s \in Z_{q}^{n}$ 이 있다. 무작위 행렬 $A \in Z_{q}^{m \times n}$ 을 고르고, 작은 오류 벡터 $e \leftarrow χ^{m}$ (가우시안 분포에서 샘플링된 작은 정수들)를 더해 $b = As + e (mod q)$ 를 계산한다. 이제 $(A, b)$ 쌍을 공개할 때, $s$ 를 찾는 것이 LWE 문제다.

오류 $e$ 가 없다면 ( $b = As$ ), 이건 단순한 연립방정식이고 가우스 소거법으로 풀린다. 하지만 조금의 잡음이 더해지면 격자 위의 CVP 문제가 되어 버리고, 이것은 현재까지 알려진 최선의 양자 알고리즘으로도 지수적 시간이 필요하다. 잡음이 암호의 핵심이다. 놀랍지 않은가?

레게브는 더 나아가 LWE를 깨는 것이 곧 격자 최단벡터 문제(SVP)를 푸는 것보다 쉽지 않다는 수학적 환원(reduction)을 증명했다. 즉, LWE의 안전성은 격자 문제의 어려움에 기반한다.

실제 암호 시스템으로의 적용을 보자. 키 교환(Key Exchange) 의 관점에서, 앨리스와 밥이 비밀 키를 교환하는 방법은 다음과 같다.

앨리스는 무작위 행렬 $A$ (공개 파라미터), 자신의 비밀 $s_{A}$ , 작은 오류 $e_{A}$ 를 갖고 $b_{A} = A^{T} s_{A} + e_{A}$ 를 밥에게 보낸다. 밥도 마찬가지로 $s_{B}, e_{B}$ 를 갖고 $b_{B} = A s_{B} + e_{B}$ 를 앨리스에게 보낸다. 앨리스는 $b_{B}^{T} s_{A} \approx s_{B}^{T} A^{T} s_{A}$ 를, 밥은 $b_{A}^{T} s_{B} \approx s_{A}^{T} A s_{B}$ 를 계산한다. 오류들 때문에 두 값은 정확히 같지는 않지만 가깝다. 이 차이를 조정(reconciliation) 프로토콜로 극복하면 공통 비밀 키가 탄생한다.

[노트 기록] LWE: $b = As + e (mod q)$ 에서 $s$ 찾기. 오류 벡터 $e$ 가 핵심. 안전성은 격자 SVP/CVP로 환원됨.

NIST가 2024년 표준으로 채택한 CRYSTALS-Kyber(현재 공식명 ML-KEM, FIPS 203) 는 이 아이디어를 더 효율적인 Module-LWE 위에 구현한 KEM(Key Encapsulation Mechanism)이다. 다항식 환(polynomial ring) $R_{q} = Z_{q} [x] / (x^{n} + 1)$ 에서 연산함으로써 키 크기를 대폭 줄였다. Kyber-768의 공개키 크기는 약 1,184바이트로, RSA-3072(약 384바이트)보다 크지만 실용 가능한 범위다. 디지털 서명 표준 CRYSTALS-Dilithium(ML-DSA, FIPS 204) 과 FALCON 도 같은 격자 기반이다.

II. 영지식 증명: 알리바바의 동굴에서 ZK-SNARK까지

앞의 색맹 예시는 직관적이었다. 이제 가장 유명한 ZKP 교과서적 예시인 알리바바의 동굴(Ali Baba Cave) 으로 구조를 정확히 이해하자. (Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children", CRYPTO 1989)

동굴에는 갈림길이 있고, 두 길은 비밀 문으로 연결된다. 증명자 페기(Peggy)는 비밀 문의 암호를 알고, 검증자 빅터(Victor)는 알고 싶지 않지만 페기가 아는지 확인하고 싶다. 프로토콜: ① 빅터는 동굴 밖에서 기다린다. ② 페기는 무작위로 A 길 또는 B 길로 들어간다. ③ 빅터가 "A 길에서 나와라" 또는 "B 길에서 나와라"를 외친다. ④ 페기가 지시대로 나온다.

페기가 암호를 안다면 항상 성공한다. 모른다면 각 라운드에서 50% 확률로만 성공한다. $k$ 번 반복하면 모르면서 성공할 확률은 $(1/2)^{k}$ 로 지수적으로 감소한다. 빅터는 페기가 암호를 안다고 확신하지만, 암호가 무엇인지 전혀 배우지 못한다. 이것이 완전성, 건전성, 영지식성 세 조건 모두를 만족한다.

이 상호작용적(interactive) ZKP를 실제 암호 시스템에 쓰려면 문제가 있다. 매번 빅터와 주고받아야 한다는 것이다. 블록체인 같은 공개 검증 환경에서는 누가 빅터 역할을 하는가? 여기에 피아트-샤미르 변환(Fiat-Shamir Transform) 이 등장한다. 상호작용에서 빅터의 무작위 챌린지를 해시 함수로 대체하는 것이다. 해시 함수의 출력은 예측 불가능하므로, 증명자가 미리 속일 수 없다. 이것이 비대화형 ZKP(Non-Interactive ZKP) 의 기반이다.

[노트 기록] 피아트-샤미르 변환: 검증자의 챌린지를 $c = H (transcript)$ (해시)로 대체 → 비대화형 증명. 랜덤 오라클 모델(ROM)에서 안전.

그런데 진짜 혁명은 ZK-SNARK(Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) 의 등장이다. "Succinct(간결한)"이라는 단어가 핵심이다. 내가 100만 번의 연산을 했다는 것을 증명할 때, 검증자는 100만 번을 다시 실행하지 않고 수십 밀리초 안에 검증할 수 있다. 이것은 블록체인에서 혁명적이다. 이더리움 노드가 모든 연산을 재실행하지 않고도 트랜잭션의 유효성을 검증할 수 있기 때문이다.

ZK-SNARK의 수학적 파이프라인을 단계적으로 따라가보자.

1단계: 산술 회로(Arithmetic Circuit)로 표현. 증명하고 싶은 계산(예: "나는 $x^{3} + x + 5 = 35$ 의 해인 $x$ 를 안다")을 덧셈과 곱셈 게이트들로 이루어진 회로로 표현한다.

2단계: R1CS(Rank-1 Constraint System)로 변환. 각 곱셈 게이트를 제약 조건으로 표현한다: $(a \cdot w) \cdot (b \cdot w) = (c \cdot w)$ . 여기서 $w$ 는 증인(witness) 벡터 — 비밀 입력과 중간 계산 결과들을 담는다.

3단계: QAP(Quadratic Arithmetic Program)로 변환. R1CS 제약들을 다항식으로 인코딩한다. 모든 제약이 만족되면, 특정 다항식이 다른 다항식으로 나누어진다는 조건으로 바뀐다. 이 다항식 나눗셈 관계를 증명하는 것이 이제 목표다.

4단계: KZG 다항식 커밋먼트(Kate-Zaverucha-Goldberg Commitment). 다항식 $f (x)$ 를 "이 다항식이 있다"고 커밋하되 내용은 숨긴다. KZG는 타원곡선 위의 이중선형 페어링(bilinear pairing) $e : G_{1} \times G_{2} \to G_{T}$ 를 이용한다.

5단계: 페어링 기반 증명 시스템. Groth16, PLONK 같은 시스템이 위 단계들을 결합해 증명 크기 수백 바이트, 검증 시간 수 밀리초의 SNARK를 만든다.

ZK-SNARK는 현재 Zcash(익명 암호화폐), zkSync/Polygon(이더리움 확장) 에서 실제로 쓰이고 있다. 그러나 ZK-SNARK는 신뢰 설정(trusted setup) 이 필요하다 — 시스템 파라미터를 생성하는 초기 의식에서 비밀값이 파기되어야 하는데, 이 과정에 누군가 속임수를 쓰면 전체가 무너진다. 이를 극복한 것이 ZK-STARK(Scalable Transparent ARguments of Knowledge) 로, 신뢰 설정 없이 해시 함수만으로 구성되며 포스트 양자 안전성도 갖는다. 증명 크기가 $O (lo g^{2} n)$ 으로 SNARK의 $O (1)$ 보다 크지만, StarkNet 등에서 이미 실용화되었다.

[노트 기록] ZK-SNARK 파이프라인: 계산 → 산술 회로 → R1CS → QAP → KZG 커밋먼트 → 페어링 증명. ZK-STARK: 신뢰 설정 불필요, 포스트 양자 안전, 증명 크기 더 큼.

III. 안전한 다자간 연산(MPC): 비밀을 공유하며 계산하다

1982년, 앤드류 야오(Andrew Yao)는 다음 질문을 던졌다. 두 백만장자가 자신의 재산을 상대에게 밝히지 않고, 누가 더 부자인지 알 수 있을까? 이것이 야오의 백만장자 문제(Yao's Millionaires' Problem) 다. 당연히 불가능할 것 같지만, 야오는 이것이 가능하다는 것을 증명했다. 이 아이디어를 일반화한 것이 MPC다.

MPC의 목표: $n$ 명의 참가자가 각자의 비밀 입력 $x_{1}, x_{2}, \dots, x_{n}$ 을 보유할 때, 서로에게 자신의 입력을 노출하지 않고 공동으로 함수 $f (x_{1}, x_{2}, \dots, x_{n})$ 를 계산한다. 예: 병원 여러 곳이 환자 데이터를 공유하지 않고 질병 패턴을 함께 분석하거나, 여러 회사가 수익을 밝히지 않고 업계 평균을 계산하는 것.

야오의 혼돈 회로(Garbled Circuits) 방법을 직관적으로 이해해보자. 앨리스는 함수 $f$ 를 부울 회로로 표현하고, 각 와이어의 두 가능한 값(0과 1)에 무작위 레이블을 붙인다. 각 게이트에 대해, 두 입력 레이블 쌍으로 출력 레이블을 암호화한 표를 만든다. 이 "혼돈 회로(garbled circuit)"를 밥에게 준다. 밥은 앨리스로부터 자신의 입력에 해당하는 레이블을 OT(Oblivious Transfer, 불가지 전송) 프로토콜을 통해 얻는다 — 앨리스는 밥이 어떤 레이블을 가져갔는지 모른다. 밥은 혼돈 회로를 순서대로 "평가"하여 최종 출력을 얻는다. 앨리스는 밥의 입력을, 밥은 앨리스의 입력을 모른다.

OT(Oblivious Transfer) 는 MPC의 빌딩 블록이다. 정의: 발신자 앨리스는 두 메시지 $m_{0}, m_{1}$ 을 갖고, 수신자 밥은 비트 $b$ 를 선택해 $m_{b}$ 를 얻는다. 앨리스는 밥이 0을 선택했는지 1을 선택했는지 모르고, 밥은 $m_{1 - b}$ 에 대한 정보를 얻지 못한다. 이것은 RSA나 ECC를 이용해 구현할 수 있다.

더 현대적인 접근은 SPDZ 프로토콜(Damgård et al., 2012) 이다. 이 프로토콜은 두 단계로 나뉜다. 전처리 단계(offline phase) 에서는 실제 입력 없이 무작위 비버 삼중항(Beaver triple) $(⟨ a ⟩, ⟨ b ⟩, ⟨ c ⟩)$ — 여기서 $c = a \cdot b$ — 를 분산 방식으로 생성한다. 온라인 단계(online phase) 에서는 실제 입력이 들어오면, 비버 삼중항을 이용해 곱셈을 안전하게 수행한다. 비버 삼중항의 원리: $x \cdot y$ 를 계산하려면, $ϵ = x - a$ 와 $δ = y - b$ 를 공개 공유한다. 그러면 $x \cdot y = c + ϵ \cdot ⟨ b ⟩ + δ \cdot ⟨ a ⟩ + ϵ \cdot δ$ 를 각 파티가 로컬로 계산할 수 있다. $a, b$ 가 숨겨져 있으므로 $x, y$ 는 노출되지 않는다.

샤미르 비밀 공유(배경 지식에서 배운)와 MPC의 연결: 덧셈은 공짜다. $⟨ x ⟩_{i} + ⟨ y ⟩_{i} = ⟨ x + y ⟩_{i}$ . 각 파티가 자신의 조각끼리 더하면 된다. 곱셈은 비용이 든다. 두 비밀을 곱하면 다항식의 차수가 두 배가 되어 임계값 조건이 깨진다. 비버 삼중항이 이를 해결한다.

[노트 기록] 비버 삼중항: $(a, b, c = ab)$ 무작위 분산 생성 → 온라인 단계에서 곱셈에 사용. SPDZ: 능동적 공격자(active adversary)에도 안전한 MPC.

3부. 프로젝트 — 손으로 씨름해야 진짜다

아래 프로젝트들은 단계별로 구성되어 있다. 정답은 없다. 막히면 더 생각하고, 더 막히면 배운 개념들을 노트에서 다시 찾아라. 40분 동안 각 문제와 진지하게 씨름하는 것이 목표다.

[프로젝트 1] LWE 암호화 미니멀 구현

다음 파라미터로 LWE 기반 단순 암호화 시스템을 Python으로 구현하라. $n = 4$ , $q = 97$ (소수), 오류 분포는 ${- 2, - 1, 0, 1, 2}$ 에서 균등 분포.

(1-A) 키 생성: 비밀 벡터 $s \in Z_{97}^{4}$ 를 무작위로 생성하고, $4 \times 4$ 행렬 $A$ 를 무작위로 생성하라. 그리고 오류 벡터 $e$ 를 샘플링하여 공개키 $b = As + e (mod 97)$ 을 계산하라. 이때 공개키는 $(A, b)$ 이고 비밀키는 $s$ 다.

(1-B) 암호화: 평문은 단일 비트 $m \in {0, 1}$ 이라 하자. 무작위 벡터 $r \in {0, 1}^{4}$ 를 선택하여 암호문을 다음과 같이 만들어라: $u = A^{T} r + e^{'} (mod 97)$ , $v = b^{T} r + e^{''} + m \cdot ⌊ 97/2 ⌋ (mod 97)$ .

(1-C) 복호화: $v - s^{T} u (mod 97)$ 를 계산하라. 결과가 0에 가까우면 $m = 0$ , $⌊ 97/2 ⌋$ 에 가까우면 $m = 1$ 로 판단해야 한다. 이 판단의 정확한 임계값(threshold)을 어떻게 설정할 것인가? 오류 벡터가 너무 크면 어떤 일이 벌어지는가? 최대 허용 오류 크기의 상한을 유도해보라.

(1-D) 보안 분석: $n = 4$ , $q = 97$ 일 때, 공격자가 무차별 대입(brute-force)으로 $s$ 를 찾으려면 몇 가지 경우를 시도해야 하는가? $n = 256$ , $q = 3329$ (실제 Kyber 파라미터)로 바꾸면 어떻게 달라지는가? 숫자로 답하라.

[프로젝트 2] 샤미르 비밀 공유와 MPC 기초

(2-A) (3, 5)-임계값 비밀 공유: 비밀 $s = 1234$ 를 5개의 조각으로 나누되, 3개가 모이면 복원 가능하도록 하라. 소수 $p = 9973$ 을 사용하라. 2차 다항식 $f (x) = 1234 + a_{1} x + a_{2} x^{2} (mod 9973)$ 을 구성하라 (계수 $a_{1}, a_{2}$ 는 자유롭게 선택). 5개의 조각 $(1, f (1)), \dots, (5, f (5))$ 를 계산하라.

(2-B) 라그랑주 보간: 3개의 조각 $(1, f (1)), (3, f (3)), (5, f (5))$ 만 가지고 $f (0) = s$ 를 복원하라. 라그랑주 보간 공식을 모른다면, 먼저 직접 유도해보라: 3개의 점을 지나는 2차 다항식을 어떻게 찾는가?

(2-C) 분산 덧셈: 앨리스( $s_{A} = 37$ )와 밥( $s_{B} = 52$ )이 자신의 수를 상대에게 알리지 않고 합 $s_{A} + s_{B} = 89$ 를 함께 계산하고 싶다. 각자 자신의 비밀을 (2,3)-임계값 방식으로 조각내어 서로 조각을 교환하는 방법을 설계하라. 최종적으로 각자 합의 조각만 가지고 합을 복원하라. 힌트: 다항식 합의 성질을 생각해보라.

(2-D) 왜 곱셈은 어려운가? 앞의 덧셈 방법을 그대로 곱셈에 적용하면 어떤 문제가 생기는가? 구체적인 예시로 설명하라. (이 질문에 대한 완전한 답이 비버 삼중항의 존재 이유다. 스스로 문제를 발견하는 것이 핵심이다.)

[프로젝트 3] ZKP 프로토콜 설계

(3-A) 이산 로그 ZKP (Schnorr Protocol): 타원곡선이나 이산 로그 구조에서 가장 유명한 ZKP는 슈노르 프로토콜(Schnorr Protocol, 1989)이다. 다음 단계를 완성하라: 공개 파라미터 $G$ (생성원), $p$ (소수). 페기는 비밀 $x$ 를 알고 $Y = x G$ 를 공개한다. 페기는 " $x$ 를 안다"를 영지식으로 증명하고 싶다. ① 페기가 무작위 $r$ 을 선택하고 $R = r G$ 를 보낸다. ② 빅터가 챌린지 $c$ 를 보낸다. ③ 페기가 응답 $z = r + c x$ 를 보낸다. 빅터는 $z G = R + c Y$ 를 확인한다. 이 프로토콜의 완전성, 건전성, 영지식성 세 조건을 각각 수학적으로 검증하라.

(3-B) 피아트-샤미르 변환 적용: 3-A의 프로토콜을 비대화형으로 변환하라. 챌린지 $c = H (R ∥ Y)$ 로 설정할 때 (여기서 $H$ 는 SHA-256, $∥$ 는 concatenation), 증명은 어떤 형태가 되는가? 검증자는 어떻게 검증하는가?

(3-C) 간단한 산술 회로 → R1CS 변환: 명제 " $x^{3} + x + 5 = 35$ 를 만족하는 $x$ 를 안다" (답은 $x = 3$ 이다. 하지만 이것을 알려주지 않고 증명해야 한다)를 산술 회로로 표현하고, R1CS 제약 조건으로 변환하라. 중간 변수를 $w_{1} = x \cdot x$ , $w_{2} = w_{1} \cdot x$ 로 정의하고, 증인 벡터 $w = (1, x, w_{1}, w_{2}, out)$ 를 구성하라. R1CS 행렬 $A, B, C$ 를 명시적으로 써라.

(3-D) 블록체인 응용 설계: 프라이버시 보존 투표 시스템을 설계하라. 각 투표자는 자신의 투표(0 또는 1)가 유효한 범위(0이거나 1임)임을 증명하되, 실제 투표 내용은 공개하지 않아야 한다. 또한 각 투표자가 정확히 한 번만 투표했다는 것도 증명해야 한다. ZKP를 어떻게 활용할 수 있는가? 높은 수준의 프로토콜 다이어그램을 그려라. 완전한 구현은 필요 없으며, 어떤 ZKP를 어느 단계에서 쓰는지 설명하면 된다.

[프로젝트 4] 종합: 격자 기반 암호 라이브러리 분석

NIST 표준 ML-KEM(CRYSTALS-Kyber)의 공식 명세 문서 또는 NIST FIPS 203을 기반으로 다음 질문에 답하라. 직접 구현하지 않아도 되고, 명세를 분석하여 답하라.

(4-A) Kyber-512, Kyber-768, Kyber-1024 세 변형의 파라미터 $(n, k, q, η_{1}, η_{2}, d_{u}, d_{v})$ 를 표로 정리하고, 각각의 NIST 보안 카테고리(I, III, V)와 대응하는 고전적 보안 비트 수를 기록하라.

(4-B) Kyber의 공개키, 비밀키, 암호문의 크기(바이트)를 RSA-3072, ECDSA-256과 비교하는 표를 만들어라. 어떤 응용에서는 Kyber가 불리하고, 어떤 응용에서는 유리한가?

(4-C) "Decapsulation failure"란 무엇인가? Kyber에서 복호화가 실패할 확률(δ)은 얼마이며, 이것이 보안에 미치는 영향은 무엇인가?

이 프로젝트들은 단순히 코드를 실행하는 것이 아니라, 수학적 구조를 손으로 추적하며 왜 작동하는지 이해하는 것이 핵심이다. 3-D의 투표 시스템은 실제로 MACI(Minimal Anti-Collusion Infrastructure)라는 이름으로 이더리움 생태계에서 사용되고 있다. 네가 설계하는 것이 실제 현장의 문제다. 막혀서 답을 못 찾더라도, 어디서 막혔는지를 정확히 파악하는 것이 이미 가장 중요한 학습이다. 배움은 정답에서 오는 것이 아니라 막힌 곳에서 온다.

이산수학 및 암호학 기초