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

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

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

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을 설명해보도록 합니다. 지금까지 본문 글과 가이드 글을 제대로 읽었다면 설명을 성공적으로 할 수 있을 것입니다.