이번 세미나는 Pairing-based Cryptography에 대해서 아는 것을 목표로 합니다.

주 교재는 ‘Guide to Pairing-Based Cryptography‘입니다.

세미나 대상은 뉴테크 프라임의 ‘블록체인 코어 개념 이해 및 구현’ 교육을 수료한 분들이나 ‘밑바닥부터 시작하는 비트코인’을 깊이 있는 수준에서 마스터 하신 분들을 대상으로 합니다.

첫 번째 세미나는 Kyoungil Bae님이 미디엄에 작성한 아래 링크된 2개의 글을 읽는 것입니다.

Pairing-based Cryptography와 BLS signature의 이해 — Part 1

Pairing-based Cryptography와 BLS signature의 이해 — Part 2

Part 1을 이해하는데 어려움이 있으시다면, 먼저 Programming Bitcoin 세미나에 참석하시길 권합니다.

Programming Bitcoin 세미나에 참석하셨던 분들은 Part 1은 복습 차원으로 읽으시면 됩니다.

Part 2는 쉽지 않은 내용입니다. 하지만 글 작성자가 많은 노력을 기울여서 설명하고 있기 때문에 미리 겁먹지 않고 꼼꼼하게 읽어나간다면 그리 어렵지 않게 소화해 내실 수 있을 것입니다.

본문 내용을 여러 번 읽어 본 후, 아래 Part 1과 Part 2 요약 내용을 다시 한 번 주의를 기울여 읽어 봅니다. 본문 내용에서 제가 다시 가공한 부분은 경어체를 사용해서 작성했습니다.

Pairing-based Cryptography(PBC)와 BLS Signature에 대해서 다룬다.
전체 문서는 세 부분으로 구성된다.
- Part 1은 PBC와 BLS signature를 이해하기 위해 꼭 필요한 수학적 개념과 타원곡선 암호학의 기초에 대해 설명한다.
- Part 2는 PBC에서 사용하는 커브의 구성과 pairing 함수에 대해 설명한다.
- Part 3은 PBC의 가장 중요한 어플리케이션인 BLS signature에 대해 설명한다. zk-SNARK에서 PBC의 역할에 대해서도 간략하게 소개한다.

Part 1

ECC를 이해하기 위한 수학적 개념은 field와 group이다. 이 중에서도 group이 중요하다.
첫 번째 그림
- our focus는 group에서는 cyclic group, field에서는 finite field이다.
암호학에서는 finite group, finite field와 이의 기초 연산(더하기, 곱하기)으로 modular 연산을 주로 이용한다.
우리가 다룰 모든 ECC (BLS signature 포함)에서 다루는 기초 수 체계는 prime N인 finite field를 다룬다.
cyclic group
- group을 modular 더하기 연산으로 만들어 내는 원소를 generator라고 한다.
- 전체 원소를 만들 수 있는 generator가 존재할 경우 그 group을 cyclic group이라 한다.
- 만약 N이 prime일 경우 0을 제외한 ZN 내의 모든 수가 generator가 될 수 있다.
- 모든 원소는 자기 자신을 N번 더할 경우 반드시 0이 된다.
ECC에서 사용하는 group이 바로 cyclic finite group이며 모든 원소가 generator가 될 수 있다.
세 번째 그림은 왜 우리가 타원곡선 암호화를 위해 유한체와 순환군을 배우는지에 대해서 잘 설명하고 있습니다.
- 타원곡선 base field를 위해 유한체를 사용합니다.
  - base field는 a, b, x, y 값으로 사용됩니다.
- 타원곡선 상의 점들의 집합은 cyclic group이 됩니다.
  - 0을 나타내는 point of infinity 점을 추가합니다.
    - 항등원에 해당한다.
    - y축의 무한한 위나 아래에 있는 평면으로 생각하면 된다.
- 유한체 상에서 유한순환군 상의 타원곡선 암호화를 적용하려면 유한체의 차수인 p와 순환군의 차수인 q(또는 n으로 표기)가 결정되어야 합니다.
다섯 번째 그림은 타원곡선 그룹 더하기 연산의 기초가 되는 negation, addition, doubling의 기하학적인 의미를 설명한다.
- negation은 한 점의 역원을 구해서 더하는 것이다. 결과는 항등원인 point of infinity가 된다.
- addition은 타원곡선 상의 두 점을 잇는 직선을 연장했을 때 세 번째 만나는 점의 x축 대칭점이 된다.
- doubling은 같은 점을 두 번 더하는 addition에 해당합니다.
- addition과 doubling의 세 번째 점은 기울기와 직선의 방정식을 사용해서 구할 수 있습니다.
  - addition은 두 점을 가지고 기울기를 구할 수 있고, doubling의 기울기는 접선의 기울기(미분)로 구할 수 있습니다.
Bitcoin과 Ethereum, 그리고 여기서 fork된 다른 블록체인들은 대부분 secp256k1 타원곡선을 쓴다.
- secp256k1은 y² = x³ + ax +b (mod p)에서 다음과 같은 값들을 사용하는 타원곡선이다.
  - a = 0, b =7
  - p, q, g 값은 열 번째 그림을 참조합니다.
    - p가 굉장히 큰 경우에는 Schoof’s algorithm을 적용해서 타원곡선 그룹 order를 도출해 낸다.
대부분의 타원곡선 기반 전자서명 알고리즘에서는 랜덤하게 개인키(scalar)를 선택한 후 여기에 generator를 곱해서 포인트 형태의 공개키를 추출한다. 따라서 많은 사람이 공유하고 사용해야 하는 타원곡선 표준에서는 모두가 동일하게 사용할 기준점(base point)인 generator를 표준화해야 한다.
타원 곡선 그룹은 스칼라 곱을 지원한다.
- 스칼라 곱은 덧셈을 스칼라 수 만큼 반복한 것에 해당한다.
- 개인키와 함께 전자서명 r과 s, 메시지 해시 등은 모두 scalar 값이며 이 값들은 타원곡선 그룹에 속하는 포인트 인 G (generator) 혹은 공개키(pk)와 다수의 곱하기 연산을 하게 된다.

Part 2

이 글은 수학적으로 기초부터 기술하기 보다는
- 먼저 현대 암호학에서 중요한 개념 중 하나인 Diffie-Hellman problem의 관점에서 Gap Group을 소개한다.
- 만약 이런 Gap Group과 Bilinear Map(즉 pairing 함수)이 있다면 할 수 있는 일을 개념적으로 설명한다.
- 이후 이를 가능하게 하는 G1, G2, GT 그룹과 pairing 함수를 레고 블록처럼 하나하나 기술하고 모든 레고 블록이 쌓여서 전체가 완성되어서 구동되는 모습을 보이도록 한다. 이 전체 모습이 바로 BLS signature이다.
이산 로그 문제
- a^x = b에서
  - b가 주어졌을 때, a를 알기 위해서 0부터 시작해서 x 값을 하나씩 증가시키는 방법 외에는 효율적으로 a 값을 구하는 알고리즘이 없는 문제를 이산 로그 문제라고 합니다.
타원 곡선 이산 로그 문제
- aG = b에서
  - G와 b 값이 주어졌을 때 이산 로그 문제와 같이 a 값을 구하는 효율적인 알고리즘이 없는 문제를 타원 곡선 이산 로그 문제라고 합니다.
DH Problem
- 제 3자가 A(g^a mod p)와 B(g^b mod p)를 알고 있을 때, g^ab mod p를 구하는 문제이다.
  - 이산 로그 문제의 형식을 띄기 때문에 DH Problem은 이산로그 문제가 됩니다.
- Computational Diffie-Hellman(CDH) Problem라고도 한다.
  - Decisional Diffie-Hellman(DDH) Problem와 대응될 때 사용됩니다.
    - 결정 문제란 이름 그대로 예(yes, true), 아니오(no, false)의 결과가 나오는 문제입니다.
    - 제 3자가 A(g^a mod p)와 B(g^b mod p)를 알고 있을 때, 누군가로 부터 받은 C가 g^ab mod p와 일치하는지 알 수 있는가의 문제입니다.
    - 검증을 위해 사용되려면 계산을 위한 효율적인 알고리즘이 존재해야 합니다.
DH Problem에 타원곡선 그룹을 사용할 수 있다.
공개키 방식의 디지털 서명이 가능하려면 CDH Problem은 풀기 불가능해야하고, DDH Problem은 효율적으로 풀 수 있어야 한다.
- 이러한 특성을 가진 타원곡선 그룹을 ‘Gap Group’ 이라고 한다.
Gap Group이 있다면
- 세 번째 그림과 같은 서명 방식이 가능해 진다.
- 메시지의 hash에 개인키를 곱하는 것만으로 서명을 할 수 있게 된다.
  - signature aggregation이나 BLS signature가 가능해 진다.
공개키와 서명에 하나의 타원곡선 그룹(gap group)을 사용하는 방식을 symmetric pairing이라 한다.
- 대부분의 실용화된 타원곡선 그룹과 BLS signature는 G1, G2라는 서로 다른 두 개의 타원곡선 그룹(그러나 order는 같은)으로 공개키와 서명을 표현한다. 이를 asymmetric pairing이라 한다.
- Gap Group은 Gap Diffie-Hellman Group이라고도 부르며, asymmetric pairing인 경우에는 Co-gap (Diffie-Hellman) group이라고도 부른다.
asymmetric pairing에서 DDH problem을 풀기 위해 쓰는 쓰이는 함수가 pairing 함수(e)이다.
- e: G1 x G2 → GT 형태로 G1과 G2에서 각각 하나의 포인트를 인수로 받아서 GT에 속하는 값(scalar)을 산출한다.
pairing 함수를 사용해서 디지털 서명의 DDH problem는 아래와 같이 푼다.
- Check e(sk*P, h*Q) == e(P, S)
  - 증명)
    - 식의 왼쪽 부분은 bilinearity의 특성에 의해 e(P, sk*h*Q)가 된다.
    - S = sk*h*Q임으로 e(P, sk*h*Q) == e(P, S)이 성립한다.

bilinearity 특성을 갖는 함수는 다음과 같은 성격을 갖는다.
- e(2P, Q) = e(P+P, Q) = e(P, Q)*e(P, Q) 혹은 e(P, 2Q) = e(P, Q+Q) = e(P, Q)*e(P, Q)
  - aP가 P를 a번 더한 값이므로 위 식을 좀 더 일반화해서 표현하면 다음과 같다.
    - e(aP, bQ) = e(P, bQ)^a = e(P, Q)^ab = e(P, aQ)^b = e(bP, aQ)
Pairing의 다른 조건으로는 non-degeneracy가 있다.
- G1의 모든 P에 대해서 e(P, Q) = 1 (GT의 항등원)이면 Q는 (타원곡선 그룹의 항등원)이다. 또한 G2의 모든 Q에 대해서 e(P, Q) = 1이면 P는 이다.
  - 쉽게 말하면 모든 P, Q에 대해서 e(P, Q) = 1 로 정의해도(constant map) bilinearity가 성립되는데, 이러지는 말자는 얘기다.

“레고 블록들: PBC의 전체 구조”에서 부터 갑자기 내용이 어려워 집니다. 주의를 기울여 꼼꼼하게 읽지 않으면 길을 잃을 수 있으니 조금 쉬고 가겠습니다.

G1
- PBC에서 주로 쓰는 타원곡선의 경우, order가 prime이 아니다.
- 타원곡선 그룹의 order가 prime이 아닐 경우
  - 타원곡선 그룹은 order의 prime divisor(약수)를 order로 가지는 cyclic subgroup을 가지게 된다.
  - prime divisor가 타원곡선 그룹의 order를 나누고, prime divisor의 제곱은 order를 나누지 않을 경우 prime divisor를 order로 가지는 subgroup은 유일하게 하나다.
    - F_p를 base field로 하는 이 subgroup이 바로 G1이며 prime order r을 가진다.
      - BLS12–381의 경우 p의 크기가 381 비트
        
        381비트는 바이트 크기로 나타낼 경우 48바이트(386비트) 크기를 갖게 됨으로, 3비트가 남는다.
        
        3비트는 특별한 용도로 사용한다.
        
        1비트는 좌표 점을 compressed form으로 표현하기 위해 사용한다.
Embedding degree (k)
- base field의 order인 p에 대해 p^k — 1 = 0 (mod r)을 만족하는 가장 작은 정수
  - p^k -1 이 r의 배수가 되는 가작 작은 k
- k가 작으면 (1에 가까우면) CDH Problem이 풀기 쉬워지고, k가 너무 크면 DDH Problem을 풀기가 굉장히 어려워진다.
  - DDH Problem이 쉽고, CDH Problem이 어려운 타원곡선 그룹이 필요하다.
PBC에 잘 맞는 타원곡선을 pairing-friendly elliptic curve라고 한다.
- embedding degree k 가 100 이하이면서 적정 수준의 크기를 가져야 한다.
- BLS12–381의 경우 embedding degree가 12이다.

G2
- F_p^k를 base field로 하는 order r을 갖는 subgroup
- k가 큰 수일 경우 p^k를 사용한 연산은 상당한 시간을 요구한다.
  - twist를 사용하면 좀 더 작은 k를 사용할 수 있음
    - twist는 타원곡선의 구조에 따라 F_p^k에서의 연산을 F_p^(k/2), F_p^(k/3), F_p^(k/4), F_p^(k/6)로 이동시킬 수 있다.
      - y² = x³ + ax + b에서 a가 0일 경우 F_p^(k/6)로 이동시킬 수 있다.
        
        BLS12–381에서 사용하는 타원곡선은 y² = x³ + 4 이므로 적용이 가능하다.
        
        F_p¹²에서의 연산을 F_p²에서 하는게 가능해 진다.
        
        이렇게 하기 위해서는 타원곡선 식 y² = x³ + 4*(1 + i)를 사용해야 한다.
        
        i는 허수
- G1에 비해 k배의 공간을 필요로 한다.
  - BLS12–381의 경우 2배의 공간을 필요로 한다.
    - 96바이트
GT
- F_p^k에서 0을 빼면 거대한 multiplicative group이 된다.
  - 그룹 연산으로 덧셈이 아니라 곱셈이 사용된다.
  - order는 p^k — 1이 된다(0을 빼므로).
  - k가 embedding degree라면, 즉 order인 p^k — 1가 r로 나눠진다면 F_p^k안에서 order r인 multiplicative cyclic subgroup을 만들 수 있다. 이게 바로 GT이다.
    - GT의 order인 r이 prime이므로 GT의 원소들이 모두 generator가 될 수 있다 (즉 GT의 원소 a는 a, a², a³, …, a^r = 1 (mod F_p^k)형태로 GT를 generate 한다). 또한 GT의 모든 원소들은 r 제곱을 했을 때 곱셈의 항등원인 1이 된다.
- G1의 좌표값과 G2의 좌표값을 인자로 해서 페어링 함수 e를 적용했을 때의 결과는 스칼라 값이 되고, GT의 원소가 된다.
- BLS12–381에서 GT의 k 값은 12이기 때문에 GT의 공간은 576 바이트(48 x 12)가 된다.
pairing 함수
- 이후 세미나를 통해서 자세히 다룰 것입니다. 여기에서는 pairing 함수가 bilinear한 속성을 가진다는 점에만 주의를 기울이도록 합니다.
- 그림 8을 설명해보도록 합니다. 지금까지 본문 글과 가이드 글을 제대로 읽었다면 설명을 성공적으로 할 수 있을 것입니다.