시그마 프로토콜과 Schnorr 식별

시그마 프로토콜에는 3개의 메시지가 있습니다. (1) 커밋: 증명자가 무작위 값에 대한 커밋먼트를 보냅니다. (2) 도전: 검증자가 무작위 도전을 보냅니다. (3) 응답: 증명자가 도전과 비밀을 사용해 계산한 응답을 보냅니다. 검증자는 수락하거나 거부합니다.

증명자는 비밀 x(개인 키)를 알고 있으며, 공개 키는 g^x mod p입니다(또는 타원 곡선 위의 점 X = x*G입니다). 목표는 x를 공개하지 않고 x를 알고 있음을 증명하는 것입니다. 이는 이산 로그 지식 증명입니다.

(1) 증명자가 무작위 r을 선택하고 커밋먼트 R = r*G를 보냅니다. (2) 검증자가 도전 c(무작위 정수)를 보냅니다. (3) 증명자가 응답 s = r + c*x를 보냅니다. (4) 검증자가 s*G == R + c*X인지 확인합니다. 참이면 수락합니다. 증명자는 x를 알고 있으며, 응답 s는 x가 있어야만 계산할 수 있습니다.

완전성: 정직한 증명자는 항상 s*G = r*G + c*x*G = R + c*X를 만족합니다. 건전성: 같은 R에 서로 다른 도전 c, c'를 사용한 두 대화 기록에서는 s, s'가 나오며, 여기서 x = (s-s')/(c-c')를 복구할 수 있습니다. 따라서 사기꾼은 같은 R에 대해 유효한 응답 두 개를 만들 수 없습니다.

시뮬레이터(x를 알지 못함)는 무작위 s와 c를 선택하고 R = s*G - c*X로 설정합니다. 이 (R, c, s)는 유효한 대화 기록 분포를 이룹니다. 검증자는 실제 대화 기록과 시뮬레이션된 대화 기록을 구별할 수 없습니다. Schnorr는 정직한 검증자 영지식입니다.

Schnorr를 비대화형으로 만들려면 검증자의 도전을 c = 해시(R || 메시지)로 바꿉니다. 증명자가 직접 c를 계산하고 응답합니다. 그 결과 누구나 검증할 수 있는 2개 원소 증명(R, s)이 만들어집니다. 이것이 Schnorr 서명 체계입니다.

서명(x, m): r ← 무작위; R = r*G; c = 해시(R||m); s = r + c*x. 서명 = (R, s). 검증: s*G == R + 해시(R||m)*X. 간결하고(P-256에서 64바이트), 일괄 검증이 가능하며, ROM에서 보안성이 증명되었습니다. Bitcoin Taproot(BIP-340)에 채택되었습니다.

C = r*G + v*H이며, H는 두 번째 독립 생성자입니다. 무작위성 r을 사용해 값 v에 커밋합니다. 결속성: 서로 다른 v로 열 수 없습니다(이산 로그). 은닉성: C가 균등하게 분포됩니다. Schnorr 기반 범위 증명과 Bulletproofs에 사용됩니다.

x1 AND x2를 알고 있음을 동시에 증명하려면 같은 도전을 사용해 Schnorr 프로토콜 두 개를 실행합니다(Fiat-Shamir를 통해 도전을 공유합니다). 검증자는 두 하위 증명이 모두 유효한 경우에만 수락합니다. 하나의 상호 작용으로 여러 명제를 증명할 수 있습니다.

어느 쪽인지 공개하지 않고 x1 OR x2를 알고 있음을 증명하려면 한 분기에 시뮬레이터를 사용해 가짜 대화 기록을 계산한 다음, 두 분기에 도전을 나눕니다. 검증자에게는 실제 도전의 합을 이루는, 모두 유효해 보이는 두 대화 기록이 보입니다. 이를 "링 서명"이라고 합니다.

Schnorr ID: 전자 여권(PACE 프로토콜). Schnorr 서명: Bitcoin Taproot, Monero(RingCT가 Schnorr OR 증명을 사용함), Signal Protocol(X3DH 키 합의). Pedersen 커밋먼트: 기밀 거래, Bulletproofs, Zcash Sapling 노트 암호화.

시그마 프로토콜: 커밋-도전-응답. Schnorr는 이산 로그를 알고 있음을 증명합니다. Fiat-Shamir는 이를 비대화형으로 만듭니다(Schnorr 서명). 다음 주제: 간결한 비대화형 증명을 위한 zk-SNARK