비밀을 말하지 않고 진실을 증명하기(feat.영지식 증명)

알리바바의 동굴에서 시작하는 영지식 증명 입문 - 비밀을 말하지 않고 진실을 증명하기

친구가 여러분에게 이렇게 말합니다: "나는 복잡한 수학 문제의 답을 알고 있어!"

여러분은 의심스럽습니다. "그럼 답이 뭔데?" 하고 묻죠.

친구가 대답합니다: "답은 말할 수 없지만, 내가 정말 알고 있다는 걸 100% 증명할 수 있어!"

증명이 불가능해 보이죠? 하지만 수학은 이런 게 가능합니다. 오늘은 영지식 증명(Zero-Knowledge Proof)이라는 개념을 함께 탐험해보겠습니다.

🏛️ 알리바바와 마법의 동굴

영지식 증명을 가장 잘 설명하는 고전적인 이야기가 있습니다. 1980년대 암호학자들이 만든 알리바바와 마법의 동굴 비유입니다.

 

이 동굴에는 특별한 비밀이 있습니다. A통로와 B통로는 뒤쪽에서 비밀문으로 연결되어 있는데, 이 문은 오직 마법의 주문을 아는 사람만 열 수 있습니다.

등장인물

👩 페기(Peggy): 마법의 주문을 안다고 주장하는 증명자
👨 빅터(Victor): 이를 검증하려는 검증자

페기는 주문을 알고 있다고 주장하지만, 그 주문이 무엇인지는 절대 말하고 싶지 않습니다. 빅터는 페기가 정말 주문을 아는지 확인하고 싶어합니다.

🎯 마법 같은 증명 과정

1단계: 페기가 동굴로 들어감

페기는 빅터가 보지 않는 사이에 동굴로 들어가서
A통로 또는 B통로 중 하나를 무작위로 선택합니다.

2단계: 빅터가 챌린지

빅터는 동굴 입구에서 외칩니다:
"A통로로 나와!" 또는 "B통로로 나와!"
(빅터도 동전을 던져서 무작위로 선택)

3단계: 페기가 응답

- 페기가 주문을 안다면: 요청받은 통로로 나올 수 있음
- 페기가 주문을 모른다면: 50% 확률로만 성공 가능

🧮 수학적 분석: 확률의 마법

이 과정을 한 번만 하면 페기가 운이 좋아서 성공할 수 있습니다. 하지만 여러 번 반복하면 어떻게 될까요?

확률 계산:

페기가 주문을 모르는 경우:
- 1번 성공 확률: 1/2 = 50%
- 2번 연속 성공 확률: 1/4 = 25%  
- 3번 연속 성공 확률: 1/8 = 12.5%
- n번 연속 성공 확률: (1/2)ⁿ

실제 예시:

10번 반복: (1/2)¹⁰ = 1/1024 ≈ 0.1%
20번 반복: (1/2)²⁰ = 1/1,048,576 ≈ 0.0001%
30번 반복: (1/2)³⁰ = 1/1,073,741,824 ≈ 0.00000009%

20번만 반복해도 사기칠 확률이 백만 분의 일이 됩니다! 이는 실질적으로 불가능한 수준입니다.

 

 

🔍 영지식 증명의 세 가지 마법 조건

알리바바 동굴 이야기가 진정한 영지식 증명이 되려면 세 가지 조건을 만족해야 합니다.

1. 완전성(Completeness): 진실은 항상 통한다

페기가 정말 주문을 안다면
→ 빅터의 요청에 항상 응답할 수 있다
→ 검증이 항상 성공한다

수학적 표현: P(Accept | 페기가 진실) = 1

직관적 이해:
마법의 주문을 정말 아는 사람은 언제든지 비밀문을 열 수 있으므로, 어느 통로로 나오라고 해도 문제없습니다.

2. 건전성(Soundness): 거짓말쟁이는 들킨다

페기가 주문을 모른다면
→ 운에만 의존해야 한다
→ 여러 번 반복하면 거의 확실히 실패한다

수학적 표현: P(Accept | 페기가 거짓) ≤ (1/2)ⁿ

직관적 이해:
주문을 모르는 사람은 비밀문을 열 수 없으므로, 처음 선택한 통로로만 나올 수 있습니다. 빅터가 다른 통로를 요청하면 나올 수 없죠.

3. 영지식성(Zero-Knowledge): 비밀은 안전하다

증명 과정에서 주문에 대한 정보가 전혀 노출되지 않음
빅터는 "페기가 주문을 안다/모른다" 외에는 아무것도 배우지 못함

직관적 이해:
빅터는 페기가 어떻게 반대편으로 갔는지 전혀 모릅니다. 주문이 무엇인지, 어떤 방식으로 문을 여는지 아무 단서도 얻을 수 없습니다.

🎲 시뮬레이터: 영지식성의 수학적 증명

영지식성을 수학적으로 엄밀하게 증명하는 핵심 개념이 시뮬레이터입니다.

시뮬레이터의 개념

시뮬레이터란 주문을 모르는 사람도 유효해 보이는 대화를 만들어낼 수 있는 알고리즘입니다.

시뮬레이터의 작동:

1. 동전을 던져 A 또는 B 선택
2. 빅터가 선택한 통로와 같다면 성공 기록
3. 다르다면 다시 시작 (이 부분은 녹화에서 제외)
4. 성공한 경우만 모아서 "증명 기록" 생성

🎭 구별 불가능성

핵심 아이디어:

실제 증명 기록 vs 시뮬레이터가 만든 가짜 기록
→ 구별할 수 없다면 진짜 증명에서 정보가 유출되지 않음

실제 증명:

• 페기: A통로 선택 → 빅터: "A로 나와!" → 페기: A로 나옴 ✅
• 페기: B통로 선택 → 빅터: "B로 나와!" → 페기: B로 나옴 ✅

시뮬레이터:

• 가상 페기: A 예상 → 빅터: "A로 나와!" → 기록: A로 나옴 ✅
• 가상 페기: B 예상 → 빅터: "B로 나와!" → 기록: B로 나옴 ✅
• 가상 페기: A 예상 → 빅터: "B로 나와!" → 기록 삭제 🗑️

두 기록이 완전히 동일하므로, 실제 증명에서 비밀 정보가 유출되지 않았음을 증명합니다!

 

 

🔢 수학으로 들어가기: 이산 로그 영지식 증명

이제 실제 암호학에서 사용하는 수학적 예제를 살펴보겠습니다. 이산 로그 문제의 영지식 증명입니다.

문제 설정

주어진 것:

소수 p = 23
생성원 g = 5  
공개값 y = 8

페기의 주장:

"나는 5ˣ ≡ 8 (mod 23)을 만족하는 x를 알고 있다"

정답 확인:

x = 3일 때: 5³ = 125 ≡ 8 (mod 23) ✅

페기는 x = 3을 알고 있지만, 이 값을 공개하지 않고 자신이 답을 안다는 것을 증명하고 싶습니다.

슈노르 프로토콜

1994년 클라우스 슈노르가 개발한 우아한 프로토콜입니다.

🎯 증명 과정:

1단계: 커밋(Commitment)

페기의 행동:
- 랜덤한 수 r = 7 선택
- t = gʳ mod p = 5⁷ mod 23 계산
- 5⁷ = 78125 ≡ 17 (mod 23)
- t = 17을 빅터에게 전송

2단계: 챌린지(Challenge)

빅터의 행동:
- 랜덤한 챌린지 c = 2 선택
- c = 2를 페기에게 전송

3단계: 응답(Response)

페기의 행동:
- s = r + c·x mod (p-1) 계산
- s = 7 + 2×3 mod 22 = 13
- s = 13을 빅터에게 전송

4단계: 검증(Verification)

빅터의 검증:
- gˢ mod p = 5¹³ mod 23 계산
- t·yᶜ mod p = 17×8² mod 23 계산

계산해보면:
- 5¹³ mod 23 = 7 
- 17×64 mod 23 = 17×18 mod 23 = 7

gˢ = t·yᶜ 이므로 검증 성공! ✅

 

 

🔍 왜 이것이 작동하는가?

수학적 증명

검증 조건: gˢ = t·yᶜ

우변을 전개하면:
t·yᶜ = gʳ·(gˣ)ᶜ = gʳ·gᶜˣ = gʳ⁺ᶜˣ

좌변:
gˢ = gʳ⁺ᶜˣ (∵ s = r + c·x)

따라서 gˢ = t·yᶜ ✅

직관적 이해
페기가 정말 x를 안다면, 수학적으로 이 등식이 항상 성립합니다. 반대로 x를 모르면 s 값을 올바르게 계산할 수 없어 검증이 실패합니다.

🎪 영지식성의 증명: 시뮬레이터 구성

슈노르 프로토콜이 정말 영지식인지 증명해보겠습니다.

시뮬레이터 알고리즘

주문을 모르는 누구나 할 수 있는 시뮬레이션:

1. 랜덤한 s' = 15, c' = 4 선택
2. t' = gˢ'/yᶜ' mod p 계산
   t' = 5¹⁵/8⁴ mod 23 = 6/7 mod 23 = 6×19 mod 23 = 22
3. 대화 기록: (t'=22, c'=4, s'=15)

검증해보면:

gˢ' = 5¹⁵ mod 23 = 6
t'·yᶜ' = 22×8⁴ mod 23 = 22×7 mod 23 = 6

gˢ' = t'·yᶜ' ✅ 유효한 대화!

🎭 구별 불가능성

실제 증명 vs 시뮬레이션:

• 둘 다 (t, c, s) 형태의 튜플 생성
• 둘 다 검증 조건 gˢ = t·yᶜ 만족
• 둘 다 동일한 확률 분포를 따름

결론: 어떤 계산으로도 실제 증명과 시뮬레이션을 구별할 수 없으므로, 실제 증명에서 비밀 정보 x가 유출되지 않습니다!

🌊 확률론적 vs 완벽한 영지식

확률론적 영지식

지금까지 본 예제들은 확률론적 영지식입니다

- 작은 확률로 사기가 가능 (예: (1/2)ⁿ)
- 하지만 반복하면 확률이 기하급수적으로 감소
- 실용적으로는 완벽한 보안

완벽한 영지식

완벽한 영지식은 사기 확률이 정확히 0인 경우입니다

- 수학적으로 더 우아함
- 하지만 구현이 더 복잡
- 대부분의 실용적 응용에서는 확률론적으로 충분

🚀 실생활 직관: 영지식 증명의 예시들

예시 1: 나이 증명

상황: 술집에서 21세 이상임을 증명해야 함
기존 방식: 신분증 제시 (생년월일, 주소 등 모든 정보 노출)
영지식 방식: "나는 21세 이상입니다"만 증명 (정확한 나이는 비공개)

예시 2: 자격 증명

상황: 명문대 졸업생임을 증명해야 함
기존 방식: 졸업증명서 제시 (성적, 전공 등 상세 정보 노출)
영지식 방식: "나는 해당 대학 졸업생입니다"만 증명 (기타 정보는 비공개)

예시 3: 재정 상태

상황: 대출 신청 시 소득 수준 증명
기존 방식: 통장 사본 제시 (모든 거래 내역 노출)
영지식 방식: "내 소득이 기준액 이상입니다"만 증명 (정확한 금액은 비공개)

🎯 마무리: 수학이 만드는 프라이버시의 새로운 패러다임

영지식 증명은 실생활에 밀접하게 쓰이진 않습니다. 하지만 디지털 시대가 되어가는만큼 온라인에서는 사기가 판치는 세상이 되어가고 있습니다. 이제 대한 활용이 될 수 있습니다. 내 정보를 노출하지 않으면서 나를 증명하는 것이 어쩌면 중요한 시대가 되어가는 게 아닌가 싶습니다.

 

내용이 장황하여 정리를 하겠습니다.

 

🔑 세 가지 조건

• 완전성: 진실한 사람은 항상 증명할 수 있다
• 건전성: 거짓말쟁이는 높은 확률로 들킨다
• 영지식성: 비밀 정보는 전혀 노출되지 않는다

📊 확률 활용

• 한 번은 운으로 속일 수 있지만
• 여러 번 반복하면 진실이 드러난다
• 수학적 확률이 보안을 보장한다

🎭 시뮬레이터

• 가짜 증명을 만들 수 있다면
• 진짜 증명에서 정보가 유출되지 않음을 의미
• 이것이 영지식성의 수학적 증거