Elliptic Curve Pairing

donghyun·2023년 3월 3일

Intro: Elliptic Curve Pairing

e: G_1 \times G_2 \to G_T

$G_1$ is typically a subgroup of $E(F_q)$

$G_2$ is typically a subgroup of $E(F_{q^k})$

실제로는 여기에 twist를 사용해 degree를 줄임

$G_T$ is a multiplicative subgroup of $F_{q^k}^*$

타원곡선에서 일반적인 pairing의 정의이다. 타원곡선에서 pairing을 사용하는 이유는 타원곡선상에는 곱셈이 존재하지 않기때문이다. $G_1$ , $G_2$ 의 타원곡선 원소쌍을 연산하여 multiplicative 그룹 $G_T$ 의 원소가 되게하는 특정 함수들이 존재하며 이들을 Pairing 함수라고 부른다. 주의할 점은, $G_1$ , $G_2$ , $G_T$ 가 같은 order을 가지며 $G_T$ 는 타원곡선 그룹의 점이 아닌 scalar값이다. 아래에서 타원곡선에서 사용할 pairing에 효과적인 group과 embedding degree $k$ , 복잡한 field상의 group 연산을 단순한 field상의 group 연산으로 전환시키는 twist에 대해서 다룬다.

Gap Diffie-Hellman Group

앞서 Elliptic Curve Pairing의 근간이 되는 Pairing(Bilinear map)에서 DDH problem을 이야기하였다. G1과 G2가 완전히 분리된 그룹이 아니라면 pairing을 사용하는 것이 DDH problem을 쉽게 만들어줄 것이다. 하지만 pairing을 효과적으로 Elliptic Curve에서 사용할 수 있으려면 CDH problem은 여전히 풀기 어려워야 하며, 이에 상충하는 CDH problem은 어렵고 DDH problem은 쉬운 적절한 타원 곡선 그룹을 골라야 한다. 이러한 그룹을 Gap Diffie-Hellman Group이라고 부른다.

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

DDH(Decisional Diffie-Hellman) problem
주어진 그룹 G와 그룹 element $g$ , $g_a$ , $g_b$ , $g_c$ 가 있을 때 $g_c$ 가 $g_{ab}$ 인지 아닌지 결정할 수 있는가 하는 문제

Embeddig degree $k$

CDH problem은 어렵고 DDH problem은 쉬운 난이도를 나타낼 수 있는 중요한 지표는 Embedding degree $k$ 가 있다. $k$ 는 base field인 $F_p$ 에 대해 $p^k - 1 = 0\ (mod\ r)$ 을 만족하는 가장 작은 정수를 말한다. 즉, $p^k-1$ 가 $r$ 의 배수가 되는 가장 작은 $k$ 를 의미한다. (참고: $r$ 은 $F_p$ 에서 subgroup을 가지는 $G_1$ 의 prime order을 의미한다). Embedding degree가 1에 가까울수록 CDH problem이 풀기 쉬워지고 너무 클수록 연산 시간이 늘어나 DDH Problem 마저도 풀기가 어려워진다. 그렇기 때문에 적절한 크기의 $k$ 를 가진 타원곡선을 사용하면 pairing에 친숙한 curve라고 부를 수 있다. 대표적으로 BN curve와 BLS curve가 있다. BLS curve에서 뒤에 붙는 숫자는 embedding degree 와 base field order크기를 나타낸다.(ex. BLS12-381,{embedding degree: 12, base field order: 381-bit})

💡 More information
연산시간이 오래걸린다는 의미는 pairing 계산이 오래걸린다는 것이며 pairing을 계산하는 pairing 함수는 현재 weil pairing, Tate pairing, ate pairing등이 있다.

Related with: divisor, miller’s algorithm

Twist

암호학에 쓰이는 타원곡선에서 finite field $p$ 도 굉장히 큰데 예를들어 $p^{12}$ 는 실제 사용하기에 너무 큰 숫자이고 연산에도 상당한 시간이 걸린다. 해결책으로 twist라는 방법이 있는데 복잡한 base field상의 group 연산을 보다 단순한 base field상의 group 연산으로 mapping 시킬 수 있는 방법이다. 수학적으로 두 group을 동형(isomorphic)이라고 한다. 모든 twist에는 degree d를 가지고 있다. Twisted curve는 $F_{p^{k/d}}$ 상에서 정의된다. 예를 들어 embedding degree $k = 2$ 일 때, twisted curve는 $F_{p^{2/2}}$ (= $F_p$ )상에서 정의 된다. 이를 quadratic twist( $d=2$ )라고 부른다. 즉, 동형이기때문에 확장필드 $F_{p^2}$ 상에서 연산을 twisted curve $E'(F_p)$ 상에서 연산할 수 있다. 또 다른 예시로 $F_{p^{12}}$ 에서 quadratic twist는 $F_{p^6}$ 에서의 연산을 수행하고 sextic twist( $d=6$ )은 $F_{p^2}$ 에서 연산이 수행된다. 대신 타원곡선의 형태가 isomorphic할 수 있도록 조금 변경된다. 아무튼, $d$ 값에 따라서 연산에 사용되는 field를 줄일 수 있기 때문에 가능한 가장 큰 $d$ 값을 선택하는게 좋다. 가능한 $d$ 값은 2, 3, 4, 6이다[J. H. Silverman. The Arithmetic of Elliptic Curves (2nd Edition), 2009]. $d$ 값을 정할때 $a,b$ 값에 따라서 제약사항이 있다.

$d=2$ , quadratic twists는 모든 타원곡선에서 가능하다. $y^2=x^3+ax+b$

$d=3$ , cubic twists는 $a=0$ 일때만 가능하다. $y^2=x^3+b$

$d=4$ , quartic twists는 $b=0$ 일때 가능하다. $y^2 = x^3 + ax$

$d=6$ , sextic twists는 $a=0$ 일때만 가능하다. $y^2= x^3+b$

💡 **More information**

Twist는 타원곡선의 구조에 따라 $F_{p^k}$ 에서의 연산을 $F_{p^(k/2)}, F_{p^(k/3)},F_{p^(k/4)},F_{p^(k/6)}$ 으로 이동시켜서 할 수 있게 해준다. BLS12-381에서는 $y^2=x^3+4$ 을 사용하기때문에 sextic twists 적용이 가능하다. $k=12$ 인데 $F_{p^{12}}$ 의 연산을 twist를 이용하여 $F_{p^2}$ 에서 할 수 있게 해준다. 다만 허수가 사용되고 타원곡선 식이 $y^2 = x^3 + 4*(1+i)$ 로 변경된다. $i$ 는 복소수(complex number)에서 쓰는 허수의 단위 $(i^2+1=0)$ . $F_{p^2}$ 의 수 연산 체계는 복소수 연산 체계를 사용한다.