서명과 영지식 증명

2025.10.10 14:57

암호학에서는 서명을 Digital signature(디지털 서명) 또는 Signature scheme(서명 체계)이라 한다.
서명 체계는 일반적으로 다음 세 가지 알고리즘으로 구성된다.
1. 서명자가 새로운 비밀키(서명키)와 공개키(검증키)를 생성하는 데 사용하는 키 쌍 생성 알고리즘
2. 비밀키와 메시지를 사용하여 서명을 생성하는 서명 알고리즘
3. 공개키, 메시지, 서명을 사용하여 성공 또는 오류 메시지를 반환하는 확인 알고리즘
서명은 메시지의 원본과 메시지의 무결성을 인증하는 데 유용하다.
- 원본(origin): 내 서명이 있는 경우 내가 보낸 것이다.
- 무결성(integrity): 누군가가 메시지를 수정하면 서명이 무효화된다.
MAC에서 생성된 인증 태그는 타이밍 공격을 피하기 위해 상수 시간에 검증되어야 했지만 서명 확인에는 공개키만 포함되므로 상수 시간에 검증되지 않아도 된다.

ZKP, zero-knowledge proof (영지식 증명)

영지식 증명은 어떤 정보(x)를 실제로 공개하지 않으면서도 그 정보를 알고 있다는 사실을 증명하는 암호학적 기법이다. 서명 체계의 중요한 요소이며, 블록체인과 프라이버시 보호 시스템에서 핵심적인 역할을 한다.
비밀 정보 x를 알고 있는 증명자는 x를 공개하지 않으면서도, 검증자에게 x를 알고 있다는 사실을 납득셔야 한다.
세 가지 속성을 충족한다
- 완전성(Completeness): 증명자가 실제로 비밀을 알고 있다면, 검증자는 항상 이를 확인할 수 있다.
- 건전성(Soundness): 증명자가 비밀을 모르면, 검증자를 속일 확률은 무시할 수 있을 정도로 낮다.
- 영지식성(Zero-Knowledge): 검증자는 “증명자가 비밀을 알고 있다”는 사실 외에는 아무것도 배울 수 없다. 즉, 비밀 자체에 대한 정보는 전혀 얻지 못한다.

Schnorr identification protocol (슈노어 식별 프로토콜)

이산 로그 문제를 기반으로하는 대표적인 대화형 영지식 증명이다.

증명자(Prover)                      검증자(Verifier)
비밀: x
공개: Y = g^x

1. 랜덤 k 선택
   R = g^k           ----R---->

2.                   <---c----   랜덤 챌린지 c 전송

3. s = k + c·x 계산  ----s---->

4.                                검증: g^s ?= R · Y^c
                                  (g^(k+c·x) = g^k · (g^x)^c)

증명자는 x를 공개하지 않고도 x를 알고 있음을 증명한다.
검증자는 c를 무작위로 선택하므로, 증명자가 x를 모르면 올바른 s를 만들 수 없다.
하지만 증명자와 검증자가 여러 번 메시지를 주고받아야 하므로 대화형이다.

비대화형 영지식 증명(NIZK, Non-Interactive Zero-Knowledge Proof)

대화형 증명은 실시간 통신이 필요하므로 블록체인처럼 비동기 환경에서는 불편하다. Fiat-Shamir 변환을 통해 대화형 프로토콜을 비대화형으로 바꿀 수 있다.

Fiat-Shamir 변환: 검증자의 랜덤 챌린지를 해시 함수로 대체한다.

대화형: 검증자가 랜덤 c를 선택
비대화형: c = Hash(R, Y, 메시지)

증명자가 스스로:
1. k 선택, R = g^k 계산
2. c = Hash(R, Y, 메시지) 계산
3. s = k + c·x 계산
4. (R, s)를 증명으로 제출

검증자는:
1. c = Hash(R, Y, 메시지) 재계산
2. g^s ?= R · Y^c 확인

증명자가 c를 미리 예측하여 조작하려면 해시 함수를 역산해야 하는데, 이는 계산적으로 불가능하다.
블록체인에서는 이 증명을 트랜잭션에 포함시키면, 누구나 나중에 검증할 수 있다.

예시

zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)
- 비대화형이며, 증명 크기가 매우 작다. (수백 바이트)
- 검증 시간이 밀리초 단위로 빠르다.
- Trusted Setup이 필요하다는 단점이 있다. (초기 설정 시 생성된 비밀이 노출되면 위조 증명 생성 가능)
- Zcash, Tornado Cash 등에서 사용된다.
zk-STARKs (Zero-Knowledge Scalable Transparent Argument of Knowledge)
- Trusted Setup이 필요 없고 양자 컴퓨터에 안전하다.
- 증명 크기가 zk-SNARKs보다 크다. (수십~수백 KB)
- StarkNet 등에서 사용된다.
Bulletproofs
- Trusted Setup이 필요 없다.
- 증명 크기가 로그 스케일로 증가한다. (수 KB)
- Monero의 기밀 거래(Confidential Transactions)에서 사용된다.

참고

암호화Diffie–Hellman 키교환 암호화대칭암호화 암호화비대칭암호화 암호화해시와 MAC 블록체인Altcoin 블록체인BFT