Pairing(Bilinear map)

donghyun·2023년 3월 3일

Bilinear map

Bilinear map은 함수이며 보통 e라고 표현한다. 정의는 집합 두개 (G1, G2) 연산해서 하나의 집합(GT)에 대응되는 것을 의미하며, 쉽게 말하면 두 개의 값을 입력으로 받아서 하나의 값을 출력하는 형태이다.

e: G_1 \times G_2 \to G_T

GT안의 요소들이 G1 G2의 요소들의 페어와 연관이 있기 때문에 bilinear map은 pairing으로 불린다.

Bilinear map 속성

Bilinear map은 bilinearity, non-degeneracy 두가지 속성을 충족한다. 가장 중요한 특성은 bilinearity이다.

bilinearity:

e(g^a,g^b) = e(g,g)^{ab}

다른 표기법 (모든 P,Q가 그룹 G의 element이고, 모든 a,b가 정수일 때)

e(aP,bQ) = e(P,Q)^{ab}

해당 조건을 만족하면 bilinear하다고 표현한다. 참고로 abstract algebra는 +,*연산이 일반적인 방식으로 일관성을 유지한다면 어떻게 정의되어있는지 상관하지 않기 때문에 다른 표기법도 존재한다.

non-degeneracy:

e ≠ 1

타원곡선에서의 예를 들면, G1의 모든 P에 대해서 e(P,Q) = 1이면 GT의 항등원이므로 Q는 타원곡선 그룹의 항등원인 𝒪(point at infinity)이다. 반대로 G2의 모든 Q에 대해서 e(P,Q) = 1이면 P는 𝒪이다. e(P,Q) = 1로 정의해도 bilinearity는 성립하지만 non-degeneracy 조건이 존재해야되는 이유이다.

bilinearity의 예시

e(aP,bQ) = e(P,bQ)^a = e(P,aQ)^b = e(bP,aQ) = e(P,Q)^{ab}

e(P,Q + R) = e(P,Q)*e(P,R)

간단한 함수로 bilinearity를 예시를 들면 e(x,y) = 2^xy일때 숫자를 대입해 확인할 수 있다.

e(3, 4+5) = 2^{3*(4+5)} = 2^{27}

e(3,4)*e(3,5) = 2^{(3*4)}*2^{(3*5)}=2^{12}*2^{15} =2^{27}

DDH(Decisional Diffie-Hellman) Problem

DDH problem은 주어진 그룹 G와 그룹 element $g$ , $g_a$ , $g_b$ , $g_c$ 가 있을때 $g_c$ 가 $g_{ab}$ 인지 아닌지 결정할 수 있는가 하는 문제이다. 그룹 G안에서 bilinear map의 기본적 특성은 DDH problem을 쉽게 만들어 준다. 하지만 G1과 G2가 완전히 분리된 그룹이라면 여기에서는 DDH problem은 여전히 어려운 문제이다.

💡 CDH(Computational Diffie-Hellman) problem
주어진 그룹 G와 그룹 element $g$ , $g_a$ , $g_b$ 가 있을때 $g_{ab}$ 를 계산할 수 있는가 하는 문제

DDH와 CDH간의 관계

CDH problem을 풀 수 있다면 DDH problem은 당연히 풀 수 있다. 역은 성립하지 않으며 즉, CDH problem이 DDH problem보다 어렵다는 뜻이다.

Use of Bilinear Map

Bilinear Map의 대표적인 예시는 Weil pairing, Tate pairing 등이 있다. Weil, Tate 두가지 pairing 모두 Miller’s algorithm을 사용해 연산된다. 구체적인 내용은 아티클 범주에서 벗어나기때문에 추후 새로운 아티클에서 다루도록 한다. Group은 주로 Elliptic curve에서 많이 사용되는데 이부분은 다음 포스트에서 다룬다.

donghyun

Blockchain

이전 포스트

개발자를 위한 Circom

다음 포스트