Crystals-Dilithium 리뷰

NIST PQC round 3까지 통과한 서명 스킴인 dilithium 논문 리뷰를 해봅니다.

PQC, lattice를 위주로 연구하는 중은 아니어서 security 관점이나 이런 부분은 잘 모르기 때문에 생략하도록 하고, 전체적으로 스킴이 어떻게 구성되어 있는 지 위주로 살펴보겠습니다.

 

dilithium 의 최종 페이퍼는 아래 링크에서 확인하실 수 있습니다.

Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé - CRYSTALS-Dilithium, Algorithm Specifications and Supporting Documentation, 2020

https://pq-crystals.org/dilithium/data/dilithium-specification-round3.pdf

---

round 3에 제출된 dilithium 을 이해하기 위해서는 사실 4개의 논문을 이해해야합니다. 4개를 모두 다 설명하기는 많으니 간략히 언급하고 넘어가도록 하겠습니다.

 

1. Vadim Lyubashevsky - Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures, 2009, ASIACRYPT

https://link.springer.com/chapter/10.1007/978-3-642-10366-7_35

 

2. Tim Guneysu, Vadim Lyubashevsky, and Thomas Poppelmann - Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems, 2012, CHES

https://link.springer.com/chapter/10.1007/978-3-642-33027-8_31

 

3. Shi Bai and Steven D. Galbraith - An Improved Compression Technique for Signatures Based on Learning with Errors, 2014, CT-RSA

https://link.springer.com/chapter/10.1007/978-3-319-04852-9_2 

 

4. Léo Ducas, Eike Kiltz, Tancrède Lepoint , Vadim Lyubashevsky, Peter Schwabe , Gregor Seiler and Damien Stehlé - CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme, 2018

https://eprint.iacr.org/2017/633.pdf 

 

4번은 dilithium의 초판으로 round 3까지 진행된 dilithium은 round 1, 2, 3을 거치면서 받은 코멘트를 적용해 업그레이드 된 것입니다. 그렇기 때문에 스킴의 주요 내용은 4번과 크게 다르지 않습니다. 

 

1번 논문은 기존의 lattice 기반의 서명이 아주 큰 크기의 공개키, 서명을 갖는데 이것을 rejection sampling 이라는 것을 통해서 크기를 줄인 논문입니다. rejection sampling 을 간단히 말씀드리면 secret 정보를 노출시키지 않는 범위이면서 서명 스킴을 만족시키는 작은 값이 나올 때까지 뽑겠다는 것입니다.

 

2번 논문은 schnorr 기반 서명 스킴 z = y + sc 꼴에서 sc 가 작은 값이라면 y 에 영향을 미치는 부분을 특정할 수 있지 않을까? 그러면 그 부분만 검증시키면 되지 않을까? 라는 아이디어로 공개키와 서명 크기를 줄인 논문입니다.

즉, y = 1111.......0000 이고 sc = 1111 이면 마지막 4bit 외에는 sc 를 더하든 안 더하든 y의 일부는 값이 같습니다.  

 

3번 논문은 2번 논문에서 활용한 기법을 이용해 조금 더 정교하게 상위 부분을 결정한 논문입니다.

 

4번 논문은 3번의 방법으로 공개키 사이즈를 줄이고, 이를 응용한 "hint" 라는 값을 이용해 서명 사이즈를 줄였습니다. 그리고 polynomial 곱셈 연산 시 NTT 가 가능하도록 parameter 세팅을 진행했습니다. 이로써 아주 빠른 키 생성, 서명 생성, 검증이 가능합니다.

 

최종적으로 round 3에 제출된 논문은 4번 논문을 조금 더 정교하게 다듬은 논문입니다.

 

해당 흐름을 바탕으로 위 논문들을 읽으면 dilithium을 이해하시는데 도움이 될 거 같습니다.

---

Dilithium을 리뷰하기에 앞서 lattice 기반 스킴이 왜 어려운지, PQC로 활용될 수 있는지 간단히 말씀드리겠습니다.

lattice를 기반으로 하는 어려운 문제 (NP) 는 SVP, CVP, SIS, LWE 등 다양하게 있습니다. 각 문제 별로 풀고자 하는 것과 reduction 관계 등을 정의할 수 있지만, 간단히 말하면 수백차원의 좌표계에 있는 점들 사이에 어떤 관계가 있는지 내가 알 수 있을까? 하는 것입니다.

예를 들어, SVP 문제는 lattice 상에서 원점에 가장 가까운 점을 찾는 문제입니다. 2차원이고 정수들로 이루어진 lattice라면 (1,0), (0,1) 등이 가장 가까운 점입니다. 그런데 차원이 수백차원일 때, 그리고 lattice를 구성하는 점이 정수만이 아닌 경우라면? 하지만 원점과는 구분되는 점이 존재한다면? 그럴 때는 과연 어떤 점이 가장 가까운 점일까? 하는 문제입니다. 이 문제를 풀기 위한 정답은 모든 점과 원점 사이의 거리를 비교해본다 입니다. 즉, 빨리 푸는 방법이 현재 알려져 있지 않습니다. 

이러한 문제를 푸는 방법이 현재 양자 컴퓨터 환경을 가정해도 푸는 방법이 알려져 있지 않기 때문에 PQC로 활용될 수 있고, RSA와 같이 기반 문제가 없는 경우와 달리, lattice 상에서의 문제라는 기반 문제가 존재하기 때문에 안전성 측면에서도 확실하기 때문에 최근 많이 연구 중입니다.  

(소인수분해가 어렵기 때문에 RSA가 어렵다고 알고 계신 경우가 많지만, 실제 관계는 RSA < 소인수분해 입니다. 즉, RSA를 풀 수 있지만, 소인수분해를 풀 수 없을 수도 있습니다. 아직 RSA != 소인수분해입니다. 반면 lattice 기반 문제 < lattice 기반 암호, 서명 등의 관계를 증명할 수 있으므로 lattice 문제가 안전함을 근거로 다양한 스킴을 설계할 수 있습니다. 해당 내용은 1번 논문 1.2 를 참고하시면 됩니다.

---

 

Dilithium에서 소개하고 있는 자신들의 기반 스킴은 아래와 같습니다.

Dilithium은 Module-LWE 기반의 스킴입니다. polynomial 로 구성된 matrix 인 module 에서 키 생성, 서명 등에 필요한 값을 추출합니다. 

Gen 의 3번 line 과 같이 LWE 임을 알 수 있고

Sign 의 8번 line 과 같이 Ay 라는 값의 상위 부분만을 쓸 거 같은 느낌이 듭니다.

그리고 11번 line 과 같이 rejection sampling 을 진행합니다.

Verify 의 1번 line 도 Az-ct 라는 값의 상위 부분만을 쓸 거 같습니다.

 

전체적으로 schnorr 서명 꼴을 하면서 LWE 를 이용하는 구조입니다.

 

이제 dilithium을 구성하는 키 생성, 서명, 검증 과정에 필요한 함수를 보면 다음과 같습니다.

 

SampleInBall 함수는 tau 개의 +-1, 나머지는 0 인 256비트 값을 리턴하는 함수입니다. 논문 상에서는 SHAKE256의 output을 SampleInBall 으로 한 번 더 섞어준다고 합니다. 

 

Power2Round 함수는 d bit를 기준으로 high, low bits를 나눕니다.

Decompose 함수는 alpha를 기준으로 high, low bits를 나눕니다. 이 때 21번 line과 같이 계산 효율성을 위해 22번 line과 같이 처리가 가능합니다. (alpha | q-1)

논문을 읽어보아도 뭔가 정확히 이해는 안 되었지만, 몇가지 예시를 넣어보면 맞음을 확인할 수 있습니다.

MakeHint 함수는 r 의 high bits 와 small z 에 대해 r+z의 high bits 가 동일한지 여부를 확인합니다. 즉, z 에 의해 발생하는 carry 가 존재하는 지 여부를 확인합니다.

UseHint 함수는 1 bit hint 를 이용해 구하고자 하는 r 의 high bits 를 정확히 구하는 함수입니다.

 

해당 함수들을 이용해 dilithium 의 키 생성, 서명 생성, 검증 등을 진행합니다.

---

노테이션에 대한 설명은 생략하고 키 생성, 서명 생성, 검증을 간략히 살펴보겠습니다.

 

dilithium의 키 생성은 아래와 같습니다.

$S_{\eta}$ 는 polynomial 의 각 coefficient 범위가 $-{\eta}$ ~ ${\eta}$ 까지입니다. 해당 링에서 secret 정보를 뽑고, ExpandA 함수는 ${\rho}$ 를 이용해 샘플링하여 A를 뽑는 함수입니다.

그리고 LWE 식 $t = As_1 + s_2$ 를 이용해 $t$를 계산합니다.

$t$ 는 d bit를 기준으로 high, low bits로 구분하게 됩니다. 여기서 $t$를 high, low bit로 구분하는 이유는 공개키로 $t_1$만을 사용하기 위해서입니다. 공개키로 전체 $t$를 사용하지 않고, high bits 만을 이용해 검증하도록 하여 작은 공개키 사이즈를 갖도록 합니다.

 

서명 생성은 아래와 같습니다.

서명 생성 시 16번 line과 같이 $Ay$ 를 $2{\gamma}_2$ 를 기준으로 high, low bits로 나눕니다. 그리고 19번 line과 같이 기존의 schnorr 기반 서명처럼 $z$를 생성합니다. 이 때 $cs_1$ 값이 secret 정보를 갖고 있고, 해당 정보가 signature에 노출되면 안 되기 때문에 21번 line과 같이 rejection sampling을 진행합니다. 

rejection sampling을 통과하면 23번 line과 같이 $w-cs_2+ct_0$ 에 $-ct0$를 더함으로써 발생하는 hint를 계산합니다.

실제로 검증 시 비교하는 $w^{\prime}_1$ 과 $w_1$ 이 같은 값을 가져야 하지만, $w_1$은 $Ay$ 의 high bits 이고 $w-cs_2$ 의 high bits = $w_1$ 임을 rejection sampling 으로 만족하고, $w-cs_2$ 의 high bits + hint = $w-cs_2 + ct_0$ 의 high bits 를 만족하게 됩니다.

 

검증은 아래와 같습니다.

검증 시 $Az-ct_1 2^d$ = $w-cs_2 + ct_0$ 를 만족하기 때문에 verifier 는 $w-cs_2+ct_0$ 의 high bits에 hint를 적용함으로써 $w-cs_2$의 high bits와 같음을 확인할 수 있습니다.

 

이를 조금 더 수학적으로 표현하면 아래와 같습니다. (논문을 보고 정리한 내용이라 논문에는 저대로 있지는 않습니다.)

이로써 correctness도 만족함을 확인할 수 있습니다.

 

---

전체적으로 설명이 부족하지만 모든 것을 다 설명드리기에는 양이 너무 많아 생략한 부분이 많습니다.

dilithium을 읽으면서 느낀 바로는 아주아주 어렵다.... 입니다.

혹여나 dilithium을 이해하고 싶으신 분들께서는 앞선 1,2,3번 논문을 먼저 보신 후 전체적인 흐름을 파악하신 뒤 dilithium을 읽으시면 조금 더 수월할 것입니다. (그래도 어렵다....) 그리고 위 설명이 진행됨을 생각하시면서 dilithium을 자세히 보시면 도움이 될 거 같습니다.

 

감사합니다.