영지식 증명 (Zero-Knowledge Proof)

"나는 비밀번호를 안다"는 것을 비밀번호를 한 글자도 보여주지 않고 상대에게 확신시킬 수 있을까? 성인 인증을 하면서 생년월일도, 이름도 넘기지 않을 수 있을까? 영지식 증명은 "안다는 사실만" 전달한다.

1. 갖춰야 할 3가지 성질

2. 알리바바 동굴 — 직접 돌려보기

고리 모양 동굴 안쪽에 마법의 문이 있고, 주문을 외워야 열린다. 증명자 페기는 A/B 중 한 쪽으로 들어가고, 검증자 빅터는 입구에서 기다리다가 무작위로 "A로 나와!" 또는 "B로 나와!"를 외친다.

• 정직한 페기(주문을 앎): 어느 쪽으로 들어갔든 문을 열고 요구한 쪽으로 나온다 → 항상 성공.
• 사기꾼 페기(주문 모름): 들어간 쪽으로만 나올 수 있다. 빅터가 그 쪽을 부르면 성공, 아니면 덜미.

3. 컴퓨터가 쓰는 방식 — 그래프 3색칠

"이 지도를 이웃한 나라끼리 다른 색이 되도록 3색으로 칠할 수 있다"를 칠하는 법은 숨긴 채 증명한다. 증명자는 색을 매번 무작위로 섞고(예: 빨강↔파랑 통째로 교체) 각 꼭짓점을 봉투에 넣어 봉인(커밋)한다. 검증자는 간선 하나를 골라 그 두 봉투만 열게 한다. 두 색이 다르면 통과. 한 번에 간선 하나만 보므로 전체 배색은 절대 노출되지 않고, 색칠이 틀렸다면 매 라운드 걸릴 확률이 있다.

4. 대화형에서 비대화형으로 (Fiat–Shamir)

위 방식들은 검증자가 실시간으로 도전을 던져야 한다. Fiat–Shamir 변환은 "검증자의 무작위 도전"을 증명자가 지금까지 만든 값들의 해시로 대체한다. 해시는 예측 불가능하므로 증명자가 미리 답을 준비할 수 없고, 그 결과 한 번에 완성되는 증명 파일이 나온다. 누구나 나중에 혼자 검증할 수 있다.

# 대화형: 여러 번 왕복
prover  → commit
verifier→ challenge (무작위 동전)
prover  → response
# ... n 라운드 반복 ...

# 비대화형 (Fiat-Shamir): 왕복 없음
challenge = hash(commit ‖ 공개정보)   # 검증자 대신 해시가 도전을 결정
proof = (commit, response)               # 이 한 덩어리를 아무나 검증

5. 어디에 쓰나