영지식 증명(Zero-Knowledge Proof, ZKP)을 공부하다 보면 '타원곡선 페어링(Elliptic Curve Pairing)'이라는 개념을 자주 접하게 됩니다. 페어링은 타원곡선이라는 '덧셈의 세계'와 또 다른 '곱셈의 세계'를 연결하는 마법 같은 다리 역할을 합니다. 타원곡선 암호는 덧셈 연산에 기반하는데, 많은 영지식 증명은 '곱셈 관계'의 검증을 필요로 합니다. 페어링은 바로 이 간극을 메워, 덧셈의 세계에 있는 값들을 이용해 곱셈 관계가 성립하는지를 검증할 수 있게 해줍니다. 이 덕분에 zk-SNARKs와 같은 고급 암호화 프로토콜이 가능해집니다. 이 글에서는 타원곡선 페어링이 무엇인지, 그리고 어떻게 영지식 증명에 사용되는지 쉽게 풀어 설명해 보겠습니다.
1. 페어링이란 무엇인가요? (기본 개념)
페어링은 간단히 말해, 특정 수학적 구조(타원곡선 위의 점들의 그룹)에 있는 두 개의 원소를 입력으로 받아, 다른 수학적 구조(곱셈 순환 그룹)에 있는 하나의 원소로 매핑(mapping)하는 함수입니다.
이 함수를 e라고 표현한다면, 다음과 같이 나타낼 수 있습니다.
e(P, Q) -> n
여기서 P는 그룹 $G_1$의 원소(타원곡선 위의 점), Q는 그룹 $G_2$의 원소(또 다른 타원곡선 위의 점)이며, 페어링 함수 e는 이 둘을 곱셈 연산이 정의된 대상 그룹 $G_T$의 원소 n으로 변환합니다. 즉, 두 개의 타원곡선 위 점을 입력받아 곱셈 세계의 원소 하나를 출력하는 함수라고 생각할 수 있습니다.
이 함수가 특별한 이유는 바로 '쌍선형성(Bilinearity)'이라는 독특한 성질 때문입니다.
2. 페어링의 핵심 성질: 쌍선형성(Bilinearity)
쌍선형성은 페어링을 암호학적으로 유용하게 만드는 가장 중요한 특징입니다. 수식으로 표현하면 조금 복잡해 보이지만, 그 의미는 생각보다 직관적입니다.
e(aP, bQ) = e(P, Q)^(ab)
이 수식이 의미하는 바를 하나씩 살펴보겠습니다.
- P와 Q는 각각 그룹 G_1, G_2의 기준점(Generator)입니다.
- a와 b는 임의의 비밀 숫자입니다.
- aP는 점 P를 a번 더한 것을 의미합니다. (타원곡선 연산에서는 덧셈이 기본입니다.)
- bQ는 점 Q를 b번 더한 것을 의미합니다.
쌍선형성의 마법은 바로 여기에 있습니다. a와 b라는 비밀 값을 모르는 상태에서도, aP와 bQ라는 값만 알면 e(P, Q)^(ab)라는 결과를 계산할 수 있다는 것입니다. 이것이 안전한 이유는 타원곡선 이산 대수 문제(ECDLP) 때문입니다. 즉, aP라는 값만으로는 비밀 값 a를 계산하는 것이 현실적으로 불가능하기 때문에, 비밀은 안전하게 유지되면서도 관계식 검증은 가능해집니다.
비유를 들어보겠습니다.
- 비밀 숫자 a를 '빨간색 물감', b를 '파란색 물감'이라고 상상해 보세요.
- aP는 '하얀색'(P)에 '빨간색 물감'(a)을 섞어 만든 '분홍색'입니다.
- bQ는 '하얀색'(Q)에 '파란색 물감'(b)을 섞어 만든 '하늘색'입니다.
이때 페어링 함수 e는 '분홍색'과 '하늘색'을 섞는 특별한 방법이라고 할 수 있습니다. 이 방법으로 색을 섞은 결과는, '빨간색'과 '파란색'을 먼저 곱해('보라색'의 농도를 결정) 기본 캔버스(e(P,Q))에 칠한 결과와 정확히 같아집니다. 핵심은, '분홍색'과 '하늘색'만 가진 사람이 원래의 '빨간색'과 '파란색'의 농도를 전혀 몰라도, 최종적으로 만들어진 '보라색'이 올바른 농도로 칠해졌는지 검증할 수 있다는 점입니다.
3. 영지식 증명에서 페어링은 어떻게 사용될까요?
영지식 증명의 핵심은 "어떤 정보를 직접 공개하지 않으면서, 그 정보를 알고 있다는 사실을 증명하는 것"입니다. 페어링은 바로 이 '검증' 과정에서 결정적인 역할을 합니다.
zk-SNARKs와 같은 증명 시스템은 보통 다음과 같은 구조를 가집니다.
- 증명자 (Prover): 어떤 비밀 정보(a, b 등)를 사용하여 계산을 수행하고, 그 결과가 올바르다는 증거(Proof)를 생성합니다. 이 증거는 aP, bQ와 같이 비밀 정보가 숨겨진 형태로 만들어집니다.
- 검증자 (Verifier): 증명자로부터 증거를 전달받습니다. 검증자는 비밀 정보(a, b)를 전혀 모르지만, 페어링의 쌍선형성 속성을 이용해 증거가 올바른지 검증할 수 있습니다.
예를 들어, 증명자가 비밀 값 a, b, c에 대해 a * b = c 라는 관계를 알고 있음을 증명하고 싶다고 가정해 봅시다. 이 과정을 단계별로 살펴보겠습니다.
- 증명자 (Prover)의 역할:
- 비밀 값 a, b, c와 공개된 기준점 P(G1 소속), Q(G2 소속)를 사용하여 다음 값들을 계산합니다.
- A = aP (G1의 점)
- B = bQ (G2의 점)
- C = cP (G1의 점)
- 계산된 값 A, B, C를 '증거'로써 검증자에게 전송합니다. 증명자는 절대 a, b, c 원본 값을 보내지 않습니다.
- 검증자 (Verifier)의 역할:
- 증명자로부터 A, B, C를 받습니다.
- 페어링 함수를 사용하여 다음 두 값을 계산합니다.
- 좌변(LHS): e(A, B)
- 우변(RHS): e(C, Q)
- 계산된 좌변과 우변의 값이 같은지 확인합니다: e(A, B) == e(C, Q)
왜 이것이 작동할까요?
검증자가 확인하는 e(A, B) = e(C, Q) 라는 등식에 증명자가 계산한 원래 값들을 대입해 보면 그 원리를 알 수 있습니다.
e(aP, bQ) = e(cP, Q)
여기서 페어링의 쌍선형성 e(xP, yQ) = e(P, Q)^(xy) 성질을 적용하면, 등식은 다음과 같이 변환됩니다.
e(P, Q)^(ab) = e(P, Q)^c
이 등식이 성립하려면 지수 부분인 ab와 c가 반드시 같아야 합니다. 따라서 검증자는 a, b, c 값을 전혀 모르면서도 a * b = c 라는 관계가 성립함을 100% 확신할 수 있습니다.
이처럼 페어링은 곱셈 관계를 덧셈 관계의 세계(타원곡선)에서 검증할 수 있도록 다리를 놓아주는 역할을 합니다. 이를 통해 복잡한 계산에 대한 영지식 증명을 간결하고 효율적으로 만들 수 있습니다.
4. 결론: 페어링, 암호학의 다재다능한 도구
타원곡선 페어링은 단순히 영지식 증명을 넘어, 현대 암호학의 여러 분야에 혁신을 가져온 핵심 기술입니다. 대표적으로 신원 기반 암호(Identity-Based Encryption), 짧은 서명(Short Signatures) 등 다양한 최신 암호 기술의 기반이 됩니다. 예를 들어 신원 기반 암호에서는 이메일 주소와 같은 임의의 문자열을 공개키로 사용하고, 페어링을 통해 해당 공개키에 맞는 비밀키를 생성하는 것이 가능해집니다.
핵심은 덧셈 관계만 확인할 수 있는 타원곡선 세계의 비밀 값들을, 곱셈 관계로 검증할 수 있는 다른 세계로 옮겨주는 '쌍선형성'이라는 다리를 놓는 것입니다. 이를 통해 비밀 정보를 직접 드러내지 않고도 그 값들이 올바른 관계를 만족하는지 검증할 수 있게 됩니다. 영지식 증명을 더 깊이 이해하기 위해서는 타원곡선 페어링의 이러한 역할과 가능성을 이해하는 것이 필수적입니다.
댓글
댓글 쓰기