저자: 드미트로 자카로프
감사의 말씀
이 글은 제가 블록스트림 연구 부서 에서 근무하는 동안 수행한 연구를 바탕으로 작성되었습니다. 저를 지원해주시고 이 주제를 연구할 기회를 주신 모든 분들께 감사드립니다.
이 글을 꼼꼼하게 검토하고 매우 유용한 제안을 해주신 Jonas Nikc에게 특별히 감사드립니다. 또한 설명상의 몇 가지 중요한 오류를 지적해 주신 Mykyta Redko에게도 감사드립니다.
소개
구글 양자 AI의 최신 논문 발표로 최초의 "암호학적으로 안전한 양자 컴퓨터(CRQC)"가 언제 등장할지에 대한 논의가 다시 불붙었습니다(솔직히 말하면, 일부에서는 거의 공황 상태에 빠지기도 했습니다). 관점 분분하지만, 모두가 동의하는 한 가지는 바로 양자 컴퓨팅에 안전한 알고리즘으로 최대한 빨리 전환해야 한다는 것입니다.
물론, 이는 이미 서비스 중인 대량 프로토콜에 필수적입니다. 특히 비트코인(및 더 넓은 블록체인 생태계)에서 자연스러운 첫 번째 단계는 양자 후(PQ) 보안 전자 서명 체계를 구축하는 것입니다. 그러나 이 첫 번째 단계조차 많은 논란을 불러일으킵니다. 다양한 대안적인 PQ 체계가 존재하지만, 이들은 모두 (a) 특정 지표에서 "분산 로그(DL)" 방식보다 현저히 열등하며(최소 16배 이상), (b) 기본 보안 가정에 대한 연구가 일반적으로 부족합니다(양자 전 방식과 비교했을 때).
현재 PQ 서명은 크게 해시 함수 기반 과 격자 기반 두 가지 범주로 나뉩니다. 블록스트림은 해시 함수 기반 암호화에 대한 풍부한 분석 및 연구 자료를 발표해 왔습니다. 예를 들어, Jonas Nick과 Mikhail Kudinov의 " 비트코인을 위한 해시 함수 기반 서명 체계 고찰 "과 Jonas Nick이 제안한 SHRIMPS 체계가 있습니다. 이제 격자 기반 암호화 방식에 대해 살펴볼 차례입니다!
중요 알림
코드 기반 구조도 존재하지만, 공개 키와 서명 크기가 너무 큽니다. 예를 들어, 주요 (이전) NIST 후보였던 LESS 의 최소 공개 키 크기는 13.9KB입니다. 따라서 현재로서는 비트코인에 적합한 옵션으로 보이지 않습니다.
이 기사의 주제는 다음과 같습니다.
앞서 언급했듯이, 우리는 격자 기반 서명 방식의 기본 개념을 분석할 준비가 되어 있습니다. 특히, 이 글을 읽고 나면 독자들은 Dilithium과 여러 격자 기반 증명 시스템(예: "격자 기반 곱 증명")에서 사용되는 "중단 기능이 있는 법정화폐 샤미르(Fiat-Shamir with aborts )" (또는 " 거부 샘플링 ")이라는 핵심 기법을 확실히 이해하게 될 것입니다. 놀랍게도, 이 기법은 이산 로그 가정을 기반으로 하는 기존 슈노르 서명의 구성 방식과 매우 유사합니다. 이 글에서는 독자들이 격자 기반 방식을 이해하고 암호학 분야에 더 쉽게 접근할 수 있도록 몇 가지 기본적인 도구를 제공합니다.
좀 더 구체적으로 말하자면, 이 글에서는 먼저 Lyubashevsky가 제안한 구조를 이해하기 위해 유명한 논문 " Trapdoor-Free Lattice Signatures "부터 살펴보겠습니다. 이 논문은 격자 암호학 분야 전체에서 가장 영향력 있는 논문 중 하나일 것입니다.
그리드에 대한 기초 소개
그리드
먼저 연구 대상을 소개하겠습니다. 우리는 $m$차원 "격자" $\Lambda \subseteq \mathbb{R}^d$를 $\mathbb{R}^d$ (d차원 실수 공간) 상의 독립적인 선형 벡터 집합 $\mathbf{b}_1,\dots,\mathbf{b}_m$의 모든 정수 선형 조합으로 정의합니다. 즉, 다음과 같습니다.
$$
\begin{equation*}
\Lambda \triangleq \left{ \sum_{i=1}^m \lambda_i\mathbf{b}_i: \lambda_1,\dots,\lambda_m \in \mathbb{Z} \right}.
\end{equation*}
$$
이를 보다 직관적으로 이해하기 위해 구체적인 예를 들어 보겠습니다. 아래 이미지는 2차원(m=d=2) 격자입니다.
그림 1. 벡터 $b_1 = (3, 1)$ 및 $b_2 = (2, 3)$로 이루어진 2차원 격자의 예. 결과 격자 $\Lambda$는 파란색 점들의 집합입니다.
처음 이 정의를 읽었을 때, "이렇게 간단한 정의가 도대체 무슨 유용한 정보를 제공할 수 있을까?"라는 생각이 들었습니다. 하지만 암호학자들이 격자가 많은 계산 난제들의 근본 구조라는 사실을 알아차리기 훨씬 전부터, 격자는 이미 18세기부터 수학적으로 유용하다는 것이 입증되어 왔습니다. 실제로 격자는 정수론이나 구면 패킹 문제(둘 다 격자 기반 및 암호 기반 암호화와 어느 정도 관련이 있음)와 같은 여러 분야에서 자연스럽게 나타납니다.
메모:
"래티스는 해시 기반 암호화에 비해 너무 미성숙하다"라는 말을 종종 듣습니다. 하지만 이는 오해입니다. 래티스는 해시 함수가 발명되기 훨씬 이전(1950년경)부터 사용되고 연구되어 왔기 때문입니다. :) 그럼에도 불구하고, 래티스는 해시 함수보다 더 풍부한 대수적 구조를 가지고 있습니다. 이러한 특성 덕분에 다중 서명이나 SNARK와 같은 더욱 발전된 암호화 프로토콜을 구현할 수 있지만, 보안 측면에서는 여전히 주의해야 합니다.
암호학에서의 격자 문제
격자 기반 암호화는 격자 $\lambda$ 상의 문제를 해결하는 것으로 귀결되는 일련의 가정을 중심으로 이루어집니다. 이러한 문제들은 현재 양자 컴퓨터로도 해결할 수 없는 것으로 여겨집니다. 이러한 가정에는 최단 벡터 문제( SVP ), 최근접 벡터 문제( CVP ), 유한 거리 디코딩( BDD ), 격자 동형 문제( LIP ), 결정론적 최단 벡터 문제( GapSVP ) 등 여러 가지가 있습니다.
이 글에서는 여러 가정 중 하나만을 소개하겠습니다.
(근사) 최단 벡터 문제($\gamma$-SVP)는 격자 $\Lambda$ 상의 "매우 짧은" 벡터를 찾는 것을 목표로 합니다. $\Lambda$에는 이 최단 벡터가 존재한다는 것을 (상대적으로 쉽게) 증명할 수 있습니다. 즉, $|\mathbf{u}|=\min_{\mathbf{v} \in \Lambda}|\mathbf{v}|$를 만족하는 $\mathbf{u} \in \Lambda$가 존재하며, 이 벡터의 길이를 $\lambda_1(\Lambda)$로 나타냅니다. 그러나 이러한 벡터를 찾는 것은 양자 컴퓨터에서도 어려운 문제로 여겨집니다. 우리는 이 문제를 " SVP "라고 부릅니다.
하지만 이러한 "순수한" SVP 에 기반한 실용적인 프로토콜을 개발하는 것은 거의 불가능합니다. 따라서 요구 조건을 완화합니다. 노름이 $\gamma\lambda_1(\Lambda)$보다 작은 벡터를 허용한다고 가정하면, $\gamma>1$이라는 조건만 필요합니다. 이렇게 수정된 문제는 $\gamma=\mathsf{poly}(\sqrt{d})$와 같이 큰 인수에 대해서도 여전히 충분히 어렵다는 것이 증명될 수 있습니다. 이 수정된 문제를 "$\gamma$ -SVP "라고 합니다. (역자 주: 노름은 벡터 공간의 벡터를 실수로 매핑하는 함수입니다. 즉, 각 노름은 벡터의 길이를 정의하는 방식에 해당하며, 노름 값은 벡터의 길이로 이해할 수 있습니다.)
이 문제는 다음 그림을 통해 설명할 수 있습니다.
* 그림 2. $\gamma$ -SVP 설명. 격자 $\Lambda'$가 벡터 $\mathbf{b}_1=(3,8)$와 $\mathbf{b}_2=(4,6)$로 생성된다고 가정합니다(참고로, 이는 위 그림 1에서 정의된 격자 $\Lambda$의 부분 격자입니다). 이 격자의 두 최단 벡터는 $\mathbf{u}=(-1,2)$와 $-\mathbf{u}$이며, 두 벡터의 길이는 모두 $\lambda_1(\Lambda')=\sqrt{5}$입니다. 이 근사 버전의 $\gamma$ -SVP 에서 $\gamma$는 대략 2.61$ 이므로, 길이가 $\sqrt{34}$보다 짧은 벡터만 찾으면 됩니다(이 범위는 그림에서 보라색 원으로 표시되어 있습니다). 예를 들어 $\mathbf{u}'=(2,-4)$의 길이는 $\sqrt{20}$입니다. 이것은 근사 SVP 에 대한 해이지만 표준 SVP 에 대한 해는 아닙니다.
짧은 정수 솔루션
암호 시스템은 ( 호크가 그랬던 것처럼) 격자 가설에 직접 기반하여 구축할 수도 있지만, 일반적으로는 대안 가설(격자 가설로 환원될 수 있음)을 사용합니다. 가장 유명한 예로는 " 단축 정수 해법 ( SIS )"과 " 오류를 통한 학습 ( LWE )"이 있습니다. 이 글에서는 전자에 대해서만 다루겠습니다.
$\mathbf{Ax}=0$이라는 선형 방정식이 있다고 가정해 봅시다. 여기서 $\mathbf{A} \in \mathbb{Z} q^{n \times m}$이고, $A$는 크기가 $n \times m$인 정수 행렬입니다. 이 방정식의 해를 구하는 것은 쉽습니다(예: 가우스 소거법). 그러나 $\mathbf{x} \in \mathbb{Z}^m$의 해가 "짧은" 형태, 즉 $|\mathbf{x}| {\infty} < \beta$ (여기서 $|\mathbf{x}| {\infty} := \min {i \in [m]}|x_i|$는 $\mathbf{x}$의 $\ell^{\infty}$ 노름)이고 $\beta \ll q$라는 조건을 만족해야 한다고 가정해 봅시다. 이는 $\mathsf{SIS}_{q,n,m,\beta}$로 표시되는 짧은 정수 해법 문제의 한 예가 되며, $q,n,m,\beta$를 신중하게 선택하면 양자 컴퓨터조차도 해결하기가 매우 어렵습니다.
(역자 주: 어떤 이유에서인지 저자가 여기서 사용한 $\ell^{\infty}$ 노름의 정의는 일반적인 정의와 다른 것으로 보입니다. 일반적인 정의에서는 요소의 최댓값을 취하므로, 정수 해법은 벡터의 모든 차원의 값이 $\beta$보다 작아야 한다는 조건을 요구합니다.)
연습문제 1. $m>\frac{n\log q}{\log(1+\beta)}$인 한, $\mathsf{SIS}_{q,n,m,\beta}$에 해가 존재함을 증명하시오.
또한, 우리는 "짧은" 벡터들의 집합을 나타내기 위해 $S_{\eta}$를 사용합니다. 즉,
$$
\begin{equation*}
S_{\eta} := {\mathbf{x} \in \mathbb{Z}^n: |\mathbf{x}|_{\infty} \leq \eta}.
\end{equation*}
$$
비균질 SIS
이 가정에 대한 핵심적인 수정은 동일한 방정식의 비균질 버전인 $\mathbf{Ax}=\mathbf{t}$를 고려하는 것입니다. 이러한 수정을 통해 탐색 가설이 아닌 결정론적 가설을 고려할 수 있습니다. 구체적으로, 우리는 다음 두 분포 $D_0$와 $D_1$을 구별하는 것이 계산적으로 어려운 문제라는 " 비균질 단정수 해 ( ISSIS )" 가설을 도입합니다.
- $D_0$: $\mathbb{Z}_q^{n \times m} \times \mathbb{Z}_q^n$에서 표본이 무작위로 선택됩니다.
- $D_1$: $A \gets_R \mathbb{Z} q^{n \times m}$을 무작위로 샘플링하고, 짧은 벡터 $\mathbf{s} \in \mathbb{Z}^m$ (즉, $|\mathbf{s}| {\infty} < \delta$)을 샘플링하고, $\mathbf{t} \gets \mathbf{As}$를 계산한 다음, 튜플 $(\mathbf{A}, \mathbf{t})$를 출력합니다.
기본 $\beta$와 $\delta$가 적절한 연관 관계를 가질 때 ISIS가 SIS 와 동등함을 증명할 수 있습니다. 이 가정을 통해 다음과 같은 키 생성 방법을 개발할 수 있습니다.
- 개인 키 는 짧은 요소들로 구성된 행렬 $\mathbf{S} \in S_{\eta}^{m \times k}$입니다.
- 공개 키는 $\mathbf{T} := \mathbf{AS}$이며, 여기서 $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$는 무작위로 샘플링됩니다.
연습문제 2. 공개키로부터 개인키를 복구하는 문제가 ISIS를 해결하는 것과 동일함을 증명하시오(단, $k = \mathsf{poly}(n)$이라고 가정함).
사건과의 관계
여러분은 이렇게 생각할지도 모릅니다. "격자는 어쩌지? 이게 격자와 무슨 관련이 있지?" 이 블로그 게시글에 맞는 한 가지 설명은 다음과 같습니다. 행렬 $\mathbf{A}$의 $\mathsf{SIS}_{q,n,m,\beta}$ 인스턴스에 대해 격자는 다음과 같이 정의할 수 있습니다.
$$
\begin{equation*}
\Lambda_A^{\perp} = {\mathbf{z} \in \mathbb{Z}^m: \mathbf{Az} = 0 ; (\text{mod} ; q)}.
\end{equation*}
$$
핵심 통찰 : $\mathsf{SIS}_{q,n,m,\beta}$를 푸는 것은 적절한 $\gamma$ 조건에서 $\gamma$ -SVP를 푸는 것과 같습니다. 이는 $\Lambda_A^{\perp}$의 정의에서 확인할 수 있습니다. 이 격자의 모든 벡터는 $\mathbf{A}\mathbf{x}=0$의 해입니다. 따라서 이 격자의 SVP를 구하려면 본질적으로 이 방정식의 짧은 정수 해를 찾아야 하며, 이는 SIS가 요구하는 바와 정확히 일치합니다.
피아트-샤미르, 중단과 함께 변환
동기 부여
우리는 격자 기반 가정을 통해 주어진 행렬 $\mathbf{A}$와 "짧은" 행렬 $\mathbf{S}$에 대해 단방향 사상 $\mathbf{S} \mapsto \mathbf{AS}$를 구성할 수 있음을 확인했습니다. 이는 이산 로그 가정이 성립하는 경우, 순환군 $\mathbb{G}=\langle a \rangle$에서 사상 $s \mapsto a^s$가 단방향인 것과 다소 유사합니다. 따라서 다음과 같은 질문을 던지게 됩니다.
그룹 곱셈 매핑 $s \mapsto a^s$를 $\mathbf{S} \mapsto \mathbf{A}\mathbf{S}$로 대체하여 Schnorr 서명 프로토콜을 "재현"할 수 있을까요?
정답은 '예'라는 것을 증명할 수 있습니다! 하지만 생각처럼 간단하지는 않은데, 바로 이 점이 '중단과 함께'라는 접두사가 붙게 된 이유입니다. 이 섹션에서는 이 아이디어를 실제로 구현하는 방법을 살펴보겠습니다.
슈노르 서명 방식
그럼 이제 슈노르 서명이 어떻게 작동하는지 살펴보겠습니다. 서명 체계를 설명한다는 것은 다음 세 가지 절차를 정의하는 것을 의미합니다.
- $\mathsf{KeyGen}(1^{\lambda}) \to (\mathsf{pk}, \mathsf{sk})$ : 키 쌍 생성;
- $\mathsf{Sign}(\mathsf{sk},\mu) \to \mathsf{sig}$: 개인 키 sk를 사용하여 메시지 $\mu$에 서명하고, 이를 통해 서명 sig 를 생성합니다.
- $\mathsf{Verify}(\mathsf{pk},\mu,\mathsf{sig}) \to {0,1}$: 공개 키 pk 와 메시지 $\mu$를 기반으로 서명 sig 를 검증합니다.
슈노르 서명은 이산 로그 가정을 기반으로 하는 서명 방식 중 가장 우아하고 효율적이며 간단한 방식이라고 할 수 있으며, 현재 비트코인에서 활발하게 사용되고 있습니다. 하지만 슈노르 인증 프로토콜 부터 시작하는 것이 좋습니다. 구체적으로, 차수 q 인 그룹 $\mathbb{G}$가 $g \in \mathbb{G}$로 생성되었다고 가정해 보겠습니다. 이때 서명자가 공개 키 $h \in \mathbb{G}$에 해당하는 개인 키 $\alpha$를 알고 있음을 증명하기 위해 (단, $g^{\alpha}=h$) 다음과 같은 상호 작용 프로토콜에 참여합니다.
* 그림 3. 키 쌍 $(\alpha,h)$ ( 여기서 $h=g^{\alpha}$*) 기반의 Schnorr 신원 인식 프로토콜
(역자 주: 상호 작용 과정은 다음과 같습니다. 서명자는 임의의 숫자 r을 선택하고 해당 숫자에 대한 그룹 값 a를 검증자에게 보냅니다. 검증자는 임의의 숫자 e를 선택하여 서명자에게 보냅니다. 서명자는 r, e 및 개인 키를 사용하여 z를 계산하고 검증자에게 제공합니다.)
피아트-샤미르 변환을 사용 하면 서명자는 해시 함수 $\mathsf{H}: \mathbb{G}^2 \to \mathbb{Z}_q$를 이용하여 $e$를 도출함으로써 검증자와의 상호 작용을 피할 수 있습니다. 구체적으로, 서명자는 챌린지 값 $e \gets \mathsf{H}(h,a)$를 계산하여 "증거" $(e,z)$를 생성합니다. 마지막으로, 서명 체계를 개발하기 위해 메시지 $\mu$도 챌린지 값 $e$의 도출 과정에 포함될 수 있습니다. 따라서 $\mathsf{Sign}(h,\mu)$는 다음과 같습니다.
- 위의 신원 인식 프로토콜과 유사하게, 임의 마스킹 스칼라 $r \gets_R \mathbb{Z}_q$에 대한 커밋먼트 $g^r$을 구성합니다.
- 도전 값을 계산합니다: $e \gets \mathsf{H}(\mu,a)$ ;
- 숨겨진 비밀 값 $\alpha$를 가리는 스칼라 $z = r + \alpha e$를 계산하고, 서명으로 $(e, z)$를 출력합니다.
마지막으로 검증자는 $e=_?\mathsf{H}(\mu, g^zh^{-e})$를 통해 서명 $(h,\mu,\sigma)$를 확인합니다.
첫 번째 시도: "格"이라는 문자가 포함된 Schnorr 서명
$\mathbf{S} \mapsto \mathbf{AS}$가 양자역학 이전 클래스 $\alpha \mapsto g^{\alpha}$와 매우 유사하다는 것을 알았으므로, 그림 4 에서와 같이 이 단방향 매핑을 Schnorr 항등 인식 프로토콜에 직접 적용해 보겠습니다. 앞서 언급한 사고방식에 따라, 이 시도는 자연스러운 첫 단계입니다(행렬 곱셈이 의미를 갖도록 r , a , e를 확정합니다).
그림 4. 키 쌍이 $(\mathbf{S},\mathbf{T})$인 "그리드" Schnorr 신원 인식 프로토콜의 첫 번째 시도 ($\mathbf{T}=\mathbf{AS}$, 여기서 $\mathbf{T} \in \mathbb{Z}_q^{n \times k}$, $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, $\mathbf{S} \in \mathbb{Z}_q^{m \times k}$).
먼저, 이 방식이 형식적으로 올바른지 살펴보겠습니다. 모든 값을 검증 방정식에 대입해 보겠습니다.
$$
\begin{equation*}
\mathbf{Az} = \mathbf{A}(\mathbf{S}\mathbf{e}+\mathbf{r}) = (\mathbf{AS})\mathbf{e}+(\mathbf{A}\mathbf{r}) = \mathbf{Te}+\mathbf{a}.
\end{equation*}
$$
그러므로 이 계획은 형식적으로는 옳습니다. 하지만 믿을 만한 계획일까요? 절대 그렇지 않습니다. 이 계획이 실패할 수 있는 방법은 수없이 많습니다. 예를 들면 다음과 같습니다.
- $\mathbf{a} \in \mathbb{Z}_q$가 주어졌을 때, 약정 방정식 $\mathbf{a}=\mathbf{Ar}$로부터 r을 쉽게 구할 수 있습니다. 사실, 이는 $\mathbb{Z}_q$에 대한 선형 방정식을 푸는 것과 같습니다.
- 약속 'a'가 구속되어 있다고 가정하더라도, 개인 키 S를 알지 못해도 방정식 $\mathbf{Az}=\mathbf{Te}+\mathbf{a}$를 만족하는 'z'를 찾을 수 있습니다. 다시 말해, 이는 임의의 ' e'를 얻은 후 선형 방정식을 푸는 것만으로 간단하게 해결될 수 있습니다.
우리는 이 지점에서 꼼짝없이 갇힌 것 같습니다.
두 번째 시도: 모든 것을 축소하기
"시도 #1"은 z를 쉽게 위조하고 r 에서 a를 쉽게 추출할 수 있기 때문에 안전하지 않다는 점에 유의하십시오. 이는 z와 r 이 이러한 선형 방정식에 해당하는 시스템의 임의의 해이기 때문입니다. SIS 가설에서 보았듯이, 이 프로토콜의 신뢰성을 확보하려면 z 와 r 모두 "짧아야" 합니다. 따라서 이 시도는 이를 달성하는 것을 목표로 합니다. 우리는 짧은 분포 $\chi^m$에서 r을 무작위로 샘플링할 것입니다( 샘플링된 값의 노름이 작은 $\varepsilon \in \mathbb{Z} {>0}$로 제한되는 $\mathbb{Z} q$ 상의 확률 분포 $\chi$가 있다고 가정해 봅시다). z (및 $\mathbf{r}+\mathbf{Se}$)를 더 짧게 만드는 것은 더 어렵습니다. r 이 이제 짧지만 Se도 짧아야 하기 때문입니다. 결과적으로 S 는 이미 작은 값이므로 e 가 짧으면 서 충분히 큰 가능한 값 집합을 갖도록 해야 합니다. 구체적으로, 우리는 집합 $B_{\kappa}$에서 샘플링할 것입니다.
$$
\begin{equation*}
B_{\kappa} := {\mathbf{x} \in \mathbb{Z}_q^k: x_i \in {0,\pm 1} ; \text{그리고 0이 아닌 $x_i$의 개수는 $\kappa$입니다.}}.
\end{equation*}
$$
솔직히 말해서, 이 집합은 (격자 기반 암호화의 많은 것들처럼) 갑자기 나타났습니다. 이 집합을 사용하는 이유는 아마도 다음과 같을 것입니다.
- 우리는 도전 과제 값들의 집합이 충분히 크기를 원합니다. 이 집합은 다음 조건을 만족합니다(아래 연습 문제 3 참조).
- 우리는 이 도전 값 집합의 모든 요소가 충분히 작기를 원합니다. 이는 모든 $\mathbf{e} \in B_{\kappa}$에 대해 $|\mathbf{e}|_{\infty}=1$이 성립하기 때문에 당연히 성립합니다.
- 이상적으로는 $B_{\kappa}$에 대한 해싱 구현이 가능한 한 간단해야 합니다. 이는 $B_{\kappa}$의 요소들을 삼진 문자열로 볼 수 있기 때문이기도 합니다.
연습문제 3. 도전값 집합 $B_{\kappa}$의 두 가지 속성을 증명하시오: (a) $#B_{\kappa}=2^{\kappa}\binom{k}{\kappa}$ (즉, 이 집합은 매우 크다); (b) 임의의 $\mathbf{S} \in S_{\eta}^{m \times k}$에 대해 $|\mathbf{Se}|_{2} \leq \eta\kappa\sqrt{m}$이 성립한다. 여기서 $|\cdot|_2$는 표준 유클리드 노름을 나타낸다(즉, z 계산에 포함될 Se 의 노름 값에 대한 적절한 경계가 존재한다).
이제 e 와 r이 모두 짧은 값이므로 z 또한 짧은 값입니다. 따라서 공격자가 큰 e 와 r을 보내는 것을 방지하려면 $|\mathbf{z}| 2$가 충분히 작은지 확인해야 합니다(즉, 특정 임계값 $\tau$보다 작은지 확인해야 합니다. 이는 $\tau:=\max {\mathbf{e} \in B_{\kappa}}|\mathbf{Se}| 2 + \mathbb{E} {\mathbf{r} \sim \chi^m}[|\mathbf{r}|_2]$로 이해할 수 있지만, 현재 논의 수준과는 무관합니다).
이러한 수정 사항을 적용한 두 번째 시도는 다음과 같았습니다.
그림 5. 키 쌍 $(\mathbf{S},\mathbf{T})$ ($\mathbf{T}=\mathbf{AS}$, 여기서 $\mathbf{T} \in \mathbb{Z}_q^{n \times k}$, $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ 및 $\mathbf{S} \in \mathbb{Z}_q^{m \times k}$)를 사용한 "그리드" Schnorr 신원 인식 프로토콜의 두 번째 시도.
이 해결책이 맞나요? 네, "첫 번째 시도"와 같은 이유로 맞습니다.
믿을 만한가요? 음, 몇 가지 "간단한" 공격 사례를 살펴보죠.
- $\mathbf{Ar}=\mathbf{a}$를 만족하는 더 짧은 r을 찾을 수 있을까요? 이는 ISIS를 푸는 것과 동일하므로 계산적으로 불가능해 보입니다.
- $\mathbf{Az}=\mathbf{Te}+\mathbf{a}$를 만족하는 더 짧은 z를 찾을 수 있을까요? (즉, S를 모르는 상태에서) 이것 또한 해결하기 어려운 ISIS 문제의 한 예입니다.
그렇다면 이제 이 계획이 믿을 만하다고 말할 수 있을까요?
아니요! :- (
하지만 그 논리는 상당히 미묘하며, 보안성 검증 과정에서 더 쉽게 파악할 수 있습니다. 간단히 설명하자면, z를 계산하는 전체 목적은 그 뒤에 숨겨진 비밀 값 S를 "숨기는" 것입니다. 그렇다면 z 와 S는 서로 독립적이라고 할 수 있을까요? 꼭 그렇지는 않습니다.
메모:
슈노르 서명의 보안 증명을 떠올리려고 한다면 다음 설명이 더 도움이 될 수 있습니다. EUF-CMA(선택 평문 공격 하에서의 위조 불가능성) 증명은 두 부분으로 구성됩니다. (a) 정직한 서명자를 시뮬레이션하는 것, (b) "포크 정리"를 사용하여 그 뒤에 숨겨진 비밀 값을 추출하는 것입니다. 그림 5 에서는 (a)를 어떻게 수행해야 하는지, 특히 z를 어디에서 샘플링해야 하는지 전혀 명확하지 않습니다. z 의 분포를 알고 있더라도 S 에 따라 달라질 수 있으며, 이는 시뮬레이션에 문제를 일으킬 수 있습니다.
이러한 이유로 우리는 z 와 S를 독립 변수로 만들어야 합니다. 하지만 어떻게 해야 할까요? 다음 아이디어가 유용할 것임을 증명할 수 있습니다.
후보 쌍 $(\mathbf{e},\mathbf{z})$을 생성할 때, 먼저 얻은 z 가 "충분히 좋은지" 확인합니다. 그렇지 않으면 z를 버리고 서명 과정을 다시 수행합니다.
이러한 이유로 이 패러다임을 "거부 샘플링" 또는 " 중단 기능을 갖춘 피아트-샤미르 변환"이라고 부릅니다. 생성된 값이 만족스럽지 않으면 서명 프로세스를 중단하기 때문입니다. 그렇다면 z 에 대해 "충분히 좋은" 값은 무엇일까요? 이를 위해 몇 가지 유용한 속성을 생성하는 특정 분포 $\chi$를 선택하고, z 와 S 사이의 통계적 거리가 무시할 수 있을 정도로 작아지는 시점을 찾습니다.
이산 가우시안 분포
도전 값 공간 $B_{\kappa}$의 선택이 임의적이라고 생각하신다면, 저 역시 격자 기반 전자 서명에 대해 처음 배우기 시작했을 때 이것이 완전히 임의적이라고 생각했던 것과 정확히 같습니다. 다음과 같이 격자 $\Lambda \subseteq \mathbb{R}^m$에 폭 매개변수(표준 편차) $\sigma \in \mathbb{R} {>0}$ 및 평균 $\mathbf{v} \in \mathbb{R}^m$을 갖는 가우시안 분포 $\Lambda \subseteq \mathbb{R}^m$을 도입합니다.
$$
\begin{equation*}
D {\mathbf{v},\sigma,\Lambda}^m(\mathbf{z}) := \rho_{\mathbf{v},\sigma}^m(\mathbf{z})/\rho_{\mathbf{v},\sigma}^m(\Lambda) ; \text{여기서} ; \rho_{\mathbf{v},\sigma}^m(\mathbf{z}) := \exp(-|\mathbf{z}-\mathbf{v}|_2^2/2\sigma^2).
\end{equation*}
$$
(역자 주: "가우시안 분포"는 "정규 분포"와 같은 의미입니다.)
여기서는 표기법을 다소 잘못 사용하여 이산 집합 $\Omega \subseteq \mathbb{R}^m$ 상의 분포를 $\rho_{\sigma}^m(\Omega)=\sum_{\mathbf{w} \in \Omega}\rho_{\sigma}^m(\mathbf{w})$로 나타냅니다. $\Lambda$가 $\mathbb{Z}^m$이고 $\mathbf{v}=0$인 경우에는 인덱스에서 $\Lambda$와 $\mathbf{v}$를 생략합니다.
이 정의는 설명이 필요할 것 같습니다. 핵심 아이디어는 격자 $\Lambda$ 상에 각 점 z가 나타날 확률이 $\exp(-|\mathbf{z}-\mathbf{v}| 2^2/2\sigma^2)$에 비례하도록 하는 것입니다. 이를 효율적인 확률 분포로 변환하기 위해서는 모든 확률을 정규화 상수 $\sum {\mathbf{w} \in \Lambda}\exp(-|\mathbf{w}-\mathbf{v}|_2^2/2\sigma^2)$로 나누어야 합니다 .
원칙적으로 이 분포를 " 이산 가우시안 분포"라고 부르는 이유는 연속 가우시안 분포와 매우 유사하기 때문입니다(밀도 함수는 $e^{-|\mathbf{z}-\mathbf{v}|^2/2\sigma^2}/\int_{\mathbb{R}^m}e^{-|\mathbf{z}-\mathbf{v}|^2/2\sigma^2}\text{d}\mathbf{z}$이고, 연속 분포에서는 분모의 적분을 계산하기 쉽습니다). 또한, 이 분포의 형태를 보면 표준 다변량 가우시안 분포임을 바로 알 수 있습니다.
그림 6. 2차원 이산 가우시안 분포. Ducas, Durmus, Lepoint, Lyubashevsky의 논문 " Lattice Signatures and Bimodal Gaussians "에서 발췌한 이미지.
이산 가우시안 분포를 사용하는 이유는 무엇입니까?
"왜 이 특정 분포를 선택하는가?"라는 질문에 대한 답은 통계학에서 연속 가우시안 분포를 사용하는 이유를 묻는 것과 비슷하다고 생각합니다. 연속 가우시안 분포는 다양한 연산에서 좋은 특성을 가지고 있기 때문에 자연스러운 선택입니다(예: 푸리에 변환 및 컨볼루션을 수행할 수 있고, 이산 가우시안 분포의 합은 통계적으로 단일 이산 가우시안 분포와 유사합니다).
하지만 우리의 문제( z 와 S를 확률적으로 독립하게 만드는 것)에서는 이산 가우시안 분포의 두 가지 속성이 필요합니다.
속성 (A) ( $D_{\sigma}^m$에서 짧은 벡터를 샘플링할 확률이 매우 높습니다 .) 모든 $\beta>1$에 대해 다음이 성립합니다.
$$
\begin{equation*}
\text{Pr}[|\mathbf{z}| 2>\beta\sigma\sqrt{m} ; | ; \mathbf{z} \gets_R D {\sigma}^m] < \beta^me^{m(1-\beta^2)/2}.
\end{equation*}
$$
* 속성 (B) ( 중심 가우스 분포와 비중심 가우스 분포의 비율은 거의 항상 유한하다*) 임의의 $\mathbf{v} \in \mathbb{Z}^m$에 대해 $\sigma=\alpha|\mathbf{v}|$인 한 다음이 성립한다.
$$
\begin{equation }
\text{Pr}[D_{\sigma}^m(\mathbf{z})/D_{\mathbf{v},\sigma}^m(\mathbf{z}) < e^{12/\alpha+1/(2\alpha^2)} ; | ; \mathbf{z} \gets_R D_{\sigma}^m] > 1 - 2^{-100}.
\end{equation }
$$
두 가지 속성에 대한 증명은 대량 수학을 필요로 합니다. 예를 들어, Lyubashevsky의 원 논문 4장을 참조하십시오. 우리는 이 "마법의" 상수 $e^{12/\alpha+1/(2\alpha^2)}$를 앞으로 $M_{\alpha}$로 표기할 것입니다.
연습문제 4. $\alpha>1$이라고 가정할 때, $M_{\alpha}$의 가능한 범위는 무엇입니까?
속성 (A) 는 직관적이라고 생각하지만(우리는 $\beta$가 1.0보다 약간 클 때 이를 사용할 것입니다), 속성 (B)가 왜 필요한지 여전히 궁금할 수 있습니다. 다음 섹션에서 이에 대해 설명하겠습니다.
샘플링 거부
이제 그림 6 에서 $\chi^m := D_{\sigma}^m$이라고 가정해 보겠습니다. z는 정확히 어떻게 분포될까요? $\mathbf{z}=\mathbf{Se}+\mathbf{r}$이고 $\mathbf{r} \sim D_{\sigma}^m$이 중심 이산 가우시안 분포이므로 z는 작은 오프셋 벡터 Se 를 갖는 "편향된" 가우시안 분포 $D_{\mathbf{Se},\sigma}^m$이 됩니다.
여기서 전통적인 특성이 중요해집니다. z 의 분포는 작은 오프셋 Se 에 따라 달라지므로, 동일한 S를 사용하여 여러 z를 관찰함으로써 공격자는 S 에 대한 정보를 얻을 수 있습니다.
이 오프셋을 제거할 수만 있다면... 그러면 다음 보조정리가 도움이 될 것입니다.
보조정리. $f$와 $g$를 두 확률 분포라고 하고, 가능한 모든 값의 집합(지지집합)을 $\Omega$로 나타내자. 모든 $\mathbb{R}_{\geq 1}$에 대해 $f(z) \leq Mg(z)$이다. 그러면 다음 분포($\widetilde{f}$라고 함)는 분포 $f$와 동일하다.
- 무작위 샘플링 $z \gets_R g$ .
- $f(z)/Mg(z)$ 확률로 $z$를 출력하고, 그렇지 않으면 1단계로 돌아갑니다.
기본적으로 이 보조정리의 핵심 아이디어는 $f$가 우리의 "목표 분포"이고 $g$가 "실제 분포"일 때, $f$와 $g$의 점들 사이에 적절한 부등식이 성립한다면, $g$에서 일부 샘플을 샘플링 값과 무관한 확률로 버림으로써 $f$의 분포를 모델링할 수 있다는 것입니다.
이 과정은 아래 그림과 같이 시각적으로 잘 표현되어 있습니다(BLISS 논문의 그림 7 과 동일하며, 매우 훌륭한 예시입니다). $f$와 $g$가 보조정리의 부등식을 만족한다고 가정하면, $Mg$는 $f$보다 큽니다. 그러면 거부 샘플링은 두 단계로 구성됩니다. 먼저 $Mg$에서 한 점을 선택하고, 그 점이 $f$보다 작으면 이를 수용합니다.
그림 7. 거부 샘플링 절차 시연. Ducas, Durmus, Lepoint 및 Lyubashevsky의 논문 " Lattice Signatures and Bimodal Gaussians "에서 발췌한 이미지.
이 보조정리가 무엇을 떠올리게 합니까? 핵심 기법은 이 보조정리를 다음과 같이 적용하는 것입니다.
- 우리의 목표 분포 $f$는 편향되지 않은 이산 가우시안 분포 $D_{\sigma}^m$입니다.
- 우리의 "진정한" 분포 $g$는 편향된 가우시안 분포 $D_{\mathbf{Se},\sigma}^m$입니다.
이 보조정리를 적용할 수 있을까요? 속성 (B) 가 핵심입니다. $D_{\sigma}^m(\mathbf{z}) \leq M_{\alpha}D_{\mathbf{Se},\sigma}^m$이 압도적인 확률로 성립하는 마법 상수 $M_{\alpha}$가 존재합니다! (더욱이, $|\mathbf{Se}|_2 \leq \eta\kappa\sqrt{m}$이라는 사실로부터 $\alpha$를 쉽게 확인할 수 있습니다. 연습문제 3을 참조하세요.)
경고하다
만일의 사태를 대비하여, $f(z) \leq Mg(z)$ 부등식이 $1-\varepsilon$의 압도적인 확률로 발생하도록 보조정리를 수정해야 합니다. 그러면 이 경우 분포 $\widetilde{f}$와 분포 $f$ 사이의 통계적 거리가 $\varepsilon/M$이 됨을 증명할 수 있습니다.
세 번째 시도: 류바셰프스키의 서명
마지막으로, 그림 2 의 해를 수정하기 위해 확률 $D_{\sigma}^m(\mathbf{z})/M_{\alpha}D_{\mathbf{Se},\sigma}(\mathbf{z})$를 갖는 $(\mathbf{e},\mathbf{z})$만 허용합니다. 이렇게 하면 아래 그림과 같이 전체 해가 수정됩니다.
그림 8. 격자 기반 슈노르 프로토콜(본질적으로 류바셰프스키 논문의 독창적인 방식)의 수정.
안전 인증 기본 사항*
메모:
다음 부분은 선택 사항입니다.
요약하자면, 서명 체계가 안전하다는 것을 증명하기 위해서는 (a) 정직한 서명자를 시뮬레이션하고 (b) 포크 정리를 사용하여 계산적으로 어려운 몇 가지 문제에 대한 해법을 도출해야 합니다.
단계 (a) 는 거부 샘플링 보조정리의 간단한 적용입니다. $\mathbf{r} \gets_R D_{\sigma}^m$을 직접 샘플링하고, 도전 값 $\mathbf{e} \gets \mathsf{H}(A\mathbf{r}, \mu) \in B_{\kappa}$을 계산하고, 후보 $(\mathbf{e}, \mathbf{z}:=\mathbf{Se}+\mathbf{r})$을 출력하는 대신, 먼저 $\mathbf{z} \gets_R D_{\sigma}^m$과 $\mathbf{e} \gets_R B_{\kappa}$을 샘플링하고, 랜덤 오라클을 $\mathsf{H}(\mathbf{Az}-\mathbf{Te},\mu) \gets로 재프로그래밍합니다. \mathbf{e}$ .
단계 (b) 는 공격자가 무시할 수 없는 확률 $\delta$로 유효한 서명 $(\mathbf{z},\mathbf{e})$를 출력할 수 있다고 가정합니다. 분기 정리 (포크 lemma)에 따르면, 공격자는 확률 $\propto \delta^2$로 또 다른 유효한 서명 $(\mathbf{z}^*,\mathbf{e}^*)$를 출력할 수 있습니다. 또한, 기본 무작위성은 동일합니다. 즉,
$$
\begin{equation*}
\mathbf{Az} - \mathbf{Te} = \mathbf{Az}^*-\mathbf{Te}^*.
\end{equation*}
$$
$\mathbf{T}=\mathbf{AS}$라는 사실을 이용하면 다음을 얻을 수 있습니다.
$$
\begin{equation*}
\mathbf{A}((\mathbf{z}-\mathbf{z}^*)+\mathbf{S}(\mathbf{e}^*-\mathbf{e})) = 0,
\end{equation*}
$$
여기서 $(\mathbf{z}-\mathbf{z}^*)+\mathbf{S}(\mathbf{e}^*-\mathbf{e})$는 선형 방정식 $\mathbf{Ax}=0$의 간략한 해입니다. 따라서 우리는 이 시그니처를 근사 SIS 인스턴스를 푸는 것으로 해석하는 축소 과정을 구성합니다.
성능
솔직히 말해서, 앞서 언급한 방식은 매우 비효율적입니다. 원 논문에서 제시된 매개변수를 사용하면 서명 크기는 19.9KB이고 공개 키 크기는 128KB입니다. 하지만 위에서 제시된 아이디어는 여러 가지 방법으로 최적화할 수 있습니다. 특히 다음과 같은 방법들이 있습니다.
거의 모든 서명은 $\mathbb{Z}_q$를 사용하지 않고 대신 $\mathcal{R}_q := \mathbb{Z}_q[X]/(X^d+1)$이라는 환을 사용합니다. 여기서 $d$는 2의 거듭제곱입니다. 이 환이 효율적인 이유는 이 글의 범위를 벗어납니다.
이산 가우시안 분포 이외의 다른 분포를 선택할 수도 있습니다. 예를 들어, BLISS 서명 방식은 이중 모드 가우시안 분포를 제안하며, 다른 측면은 위의 구성과 거의 동일합니다. 결과적으로 서명 크기는 5.6KB이고 공개 키 크기는 7KB입니다. 그러나 이 방식은 사이드 채널 공격에 취약한 것으로 밝혀졌습니다.
이산 가우시안 분포를 균일 분포로 바꾸면 딜리튬 방식이 됩니다. 하지만 거부 샘플링 접근 방식은 상당히 달라지고 (어떤 의미에서는 단순화될 것으로 예상됩니다).
다음 단계
본 논문에서는 격자 기반 전자 서명 방식의 핵심 패러다임인 중단 기능이 있는 피아트-샤미르 변환을 분석합니다. 이 변환은 많은 구성에서 나타나고 대부분의 논문에서 암묵적으로 사용되지만, Falcon 과 Hawk 방식 을 이해하는 데 필수적인 " 해시-앤- 서명"이라는 또 다른 패러다임이 있습니다. 이 방식들은 격자와 계약을 직접 활용합니다. 먼저 메시지 $\mu$를 $\mathbb{Z}^{2n}$ 상의 한 점으로 해싱한 다음, 이 점을 격자의 특정 기하학적 특징( Hawk 에서는 개인 키가 특정 격자의 짧은 기저 벡터 B 이고 공개 키는 그 제곱 형태인 $\mathbf{B}^{\top}\mathbf{B}$이며, Falcon에서는 공개 키가 격자의 기저이고 개인 키는 직교 격자의 기저)을 사용하여 변환합니다.
이러한 방향은 학계와 산업계 모두에서 지속적인 관심을 받고 있으며, 그럴 만한 이유가 있습니다. 저희는 이러한 아이디어들을 적극적으로 탐구하고 있으며, 향후 블로그 게시물에서 다시 다룰 예정입니다.
(위에)
