BGV Scheme (1)

A Candidate Scheme

1980년에 나온 이 scheme은 (semantically) secure하지 않으나, 이어서 나오는 LWE(Learning With Errors)와 깊은 관련이 있습니다. 한 번 알아보도록 합시다.

이 scheme의 setup 과정은 다음과 같습니다.

$2$개의 parameter, $n$과 $q$를 정합니다. $n$은 key의 dimension을 뜻하고, q는 modulus를 뜻합니다. 이전 글에서 BGV Scheme은 Finite Field $\mathbb{Z}_q$에서 동작한다고 언급했는데, 이 때 $q$와 동일한 notation입니다.

이후, key generation 과정을 거칩니다.

Secret key $\mathbf{s}=(s_1, s_2, \cdots, s_n) \in \mathbb{Z}^n$이며, 이 때 $s$는 dimension $n$의 벡터가 됩니다.

두 과정 이후, Encryption과 Decryption 과정을 다음과 같이 정의합니다.

Encryption
암호화하고자 하는 메시지 $m\in \mathbb{Z}$이 우선 존재합니다. Sample이라고 하는 크기 $n$의 벡터 $\mathbf{a}$를 다음과 같이 생성합니다: $\mathbf{a}=(a_1, a_2, \cdots, a_n)\leftarrow U(\mathbb{Z}^n_q).$ 이는, $\mathbb{Z}_q$에서 $n$개의 수를 독립적으로 random하게 뽑아 $a_1, \cdots, a_n$에 할당하는 것을 의미한다고 말할 수 있습니다. 이 때, $a_0:=-(a_1s_1+\cdots+a_ns_n)+m \mod{q}$를 정의하며 계산합니다. 메시지 $m$을 암호화한 결과는 크기 $m+1$의 벡터, $\mathbf{c}=(a_0, a_1, \cdots, a_n)\in \mathbb{Z}_q^{n+1}$이 됩니다.

Decryption
암호화된 결과 $\mathbf{c}=(a_0, a_1, \cdots, a_n)$에 대해 Decryption을 시도하는 user가 알고 있는 secret key $\mathbf{s}=(s_1, \cdots, s_n)$에 대하여, Encryption 과정에서 $a_0$의 정의로부터 $m=a_0+a_1s_1+\cdots+a_ns_n \mod{q}$가 됩니다.

과연 이 scheme은 legit할까요? scheme이 legit함은, $\mathrm{Dec}(\mathrm{Enc}(m))=m$이 됨을 의미합니다. 잘 생각해보면, 특정 조건이 만족된다면 이는 legit함을 관찰할 수 있습니다. 그 특정 조건은, $\lvert m\rvert<\frac{1}{2}q$란 사실을 생각해볼 수 있습니다. 가능한 $m$의 구간의 길이가 $q$ 미만이어야 modular 연산에 의한 값의 달라짐이 발생하지 않습니다.

한편, 마지막으로 한 번 생각해 봅시다. 이 scheme은 (semantically) secure할까요? 우선 chosen-plaintext attack과 같은 경우에는, 이 scheme은 취약하게 됩니다. 만약 $n$개 이상의 message가 $0$인 plaintext-ciphertext 쌍이 주어졌다고 가정해 봅시다. $i$번째 ciphertext $c_i=(a_{i,0}, a_{i,1}, \cdots, a_{i, n})$에 대해 $a_{i,0}+a_{i,1}s_1, \cdots, a_{i, n}s_n\equiv 0 \mod{q}$가 됩니다. 이러한 식이 성립하므로, 다음과 같은 식을 통해 secret key의 벡터 $\mathbf{s}$를 구할 수 있습니다.

\[\begin{pmatrix} a_{1, 0} \\ a_{2, 0} \\ \vdots \\ a_{n, 0}\end{pmatrix}+\begin{pmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{pmatrix}\begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_n \end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ \vdots \\ 0\end{pmatrix}\]

정확히 어떻게 구할 수 있을까요?​ 임의의 random matrix가 invertible일 확률은 $1$에 수렴하므로, 위의 $a_{1, 1}$부터 $a_{n, n}$까지 표기된 행렬의 역행렬을 구한 뒤 양변에 곱하면 secret key를 얻을 수 있고, 따라서 위 scheme은 secure하지 않습니다.

Learning with Errors

LWE Problem은 Oded Regev에 의해 2005년 제기된 computational problem입니다. LWE Problem에서 사용하는 scheme은 A Candidate Scheme의 그것과 매우 유사한데, 한 가지 차이점만 존재합니다.

LWE distribution은 \(\mathrm{LWE}_{n, q, \sigma}(\mathbf{s})\) 로 표기하며, $3$개의 parameter $n, q, \sigma$로 이루어져 있습니다. $n$은 dimension, $q$는 modulus로 앞에서와 동일하지만, $\sigma$가 새로 추가되었습니다. 이는 표준편차를 나타내는데, 이는 표준편차 $\sigma$인 discrete gaussian distribution $D_\sigma$에서 정수 $e$를 추출하는 데 쓰입니다. 이 때, discrete gaussian은 다음과 같은 형태의 확률분포를 의미합니다.

LWE instance는 우선 input으로 secret vector $\mathbf{s}$를 가집니다. 또한, 전에 다뤘던 scheme과 동일하게 \(\mathbb{Z}_q\)에서 $n$개의 수를 random하게 추출해 sample $a_1, \cdots, a_n$을 정합니다. 또한, 이전에 설명한 대로 discrete gaussian $D_\sigma$에서 임의의 정수 $e$를 추출합니다. 이후, $a_0=-(a_1s_1+\cdots+a_ns_n)+e\mod{q}$를 정하고, $(a_0, a_1, \cdots, a_n)\in \mathbb{Z}_q^{n+1}$을 반환합니다.

이제 LWE Problem은, 과연 아까처럼 적당히 원하는 plaintext-ciphertext pair가 주어지면 secret key를 찾을 수 있는지의 유무입니다. 이는 현재까지 굉장히 어렵다고 알려져 있으며, quantum computing으로도 저격하기 힘든 것으로 알려져 있습니다. 괜찮은 아이디어가 생각나신다면 블로그의 이메일로 연락 주세요.

이제 여기서, 두 가지 질문이 있습니다. 하나는 유명한 질문이고, 두 번째는 필자도 모르는 open question입니다.

LWE assumption은 두 가지 버전이 있습니다.

• Computational version: 아까 이야기한 내용과 동일합니다. 많은 $\mathrm{LWE}_{n,q,\sigma}(\mathbf{s})$의 sample이 존재했을 때 $\mathbf{s}$를 찾기 어려운지의 유무입니다.
• Decisional version: 두 distribution $\mathrm{LWE}_{n,q,\sigma}(\mathbf{s})$와 $U(\mathbb{Z}_q^{n+1})$이 구별 불가능한지의 유무에 대한 내용입니다.

상식적으로 Decisional version을 풀면 Computational version은 자명해 보입니다. 하지만 과연 역은 성립할까요? 성립합니다. 이를 증명할 수 있으며, 자세한 내용은 생략합니다. 즉, 두 assumption은 equivalent한 관계라는 사실을 알 수 있습니다.

한편, 저도 모르는 질문 하나를 남깁니다. 왜 여기서 gaussian distribution을 사용했을까요? 그 이유가 궁금합니다.

+ 추가: 다음 링크에 뭔가 답이 있는 것 같습니다. 아시는 분은 댓글 좀…

BGV Scheme (Before Linearization)

BGV Scheme은 기본적으로 parameter $n, q$를 설정하고, LWE에서 등장했던 $\sigma=3.2$를 대입하는 것으로 Setup이 진행됩니다. 이 때, $q$는 홀수가 되어야 합니다. 이후 key를 생성하는데, \(\mathbb{Z}^n\)에서 $n$개의 수 $s_1, \cdots, s_n$을 뽑아 secret key $\mathbf{s}=(s_1, \cdots, s_n)$을 생성합니다. 이후 Encryption과 Decryption을 다음과 같이 정의합니다.

Encryption
암호화하고자 하는 비트 $m\in{0,1}$를 암호화해봅시다. 위 두 방법처럼 sample $a_1, \cdots, a_n$을 \(U(\mathbb{Z}_q)\)에서 random하게 뽑고, 설정한 $\sigma=3.2$에 대해 $D_\sigma$에서 $e$를 추출합시다. 이후 $r=m+2e$로 설정하고, $a_0:=-(a_1s_1+\cdots + a_ns_n)+r\mod{q}$로 설정합시다. 이후, encryption의 결과는 길이 $n+1$의 vector \(\mathbf{c}=(a_0, a_1, \cdots, a_n)\in \mathbb{Z}^{n+1}_q\)가 됩니다.

Decryption
암호화된 결과 $\mathbf{c}=(a_0, a_1, \cdots, a_n)$에 대해 Decryption을 시도하는 user가 알고 있는 secret key $\mathbf{s}=(s_1, \cdots, s_n)$에 대하여, Encryption 과정에서 $a_0$의 정의로부터 $m+2e=r=a_0+a_1s_1+\cdots+a_ns_n \mod{q}$가 됩니다. 이후, $r$에 modulo 2를 취해주면 항 2e가 사라지므로, m만 남게 됩니다. 즉, $m=r\mod{2}$가 decryption의 결과가 됩니다.

한편, 이 scheme은 올바를까요? A Candidate Scheme과 마찬가지로, $\lvert r\rvert <\frac{1}{2}q$인 경우에는 올바르게 동작한다는 사실을 생각해볼 수 있습니다. 한편, 이 Scheme의 semantic security는 어떨까요? 결론적으로 말하면, \(E(\mathbf{s}, 0)\approx_c E(\mathbf{s}, 1)\)이 성립합니다. 이는 LWE assumption 아래에서 증명 가능한데, 당장 \(E(\mathbf{s}, 0)=2\times \mathrm{LWE}_{n,q,\sigma}(\mathbf{s})\approx_c \mathrm{unif}(\mathbb{Z}_q^{n+1})\)이기 때문입니다.

Addition
이후 연산은 모두 두 ciphertext 간의 이항 연산으로 정의됩니다. \(\mathbf{c}=(a_0, a_1, \cdots, a_n), \mathbf{c'}=(a'_0, a'_1, \cdots, a'_n)\)이라고 정의합시다. 이 때 두 ciphertext 간의 덧셈 \(c_{add}\)는 \(c_{add}=c+c'\mod{q}\)로 계산할 수 있습니다. BGV Scheme이 addition에 대해 homomorphic함을 알아봅시다. \(c_{add}\)에서의 $r$값 \(r_{add}\)에 대해 \(r_{add}=(a_0+a'_0)+\sum_{i=1}^{n}(a_i+a'_i)s_i\mod{q}=r+r'\)이므로, 여기에 modulo 2를 취하면 \(\mathrm{Dec}(\mathbf{c+c'})=m_1+m_2\)가 됩니다. 물론, \(\lvert r+r'\rvert <\frac{1}{2}q\)이어야 합니다.

Multiplication
안타깝게도 Multiplication은 조금 더 복잡합니다. Addition 과정과 동일하게 두 ciphertext \(\mathbf{c}=(a_0, a_1, \cdots, a_n), \mathbf{c'}=(a'_0, a'_1, \cdots, a'_n)\) 간의 이항 연산이며, 결론적으로 말하면 차원이 $(n+1)$차원에서 $(n+1)^2$차원으로 늘어나게 됩니다. 우선 두 vector 간의 multiplication \(c_{mul}\)은 $c$와 $c’$ 간의 tensor product \(c\otimes c'=(b_{0, 0}, b_{0, 1}, \cdots, b_{i, j}, \cdots, b_{n, n})\in \mathbb{Z}_q^{(n+1)^2}\)으로 정의됩니다. 이 때, tensor product의 정의에 의해 \(b_{i, j}=a_i\times a'_j\mod{q}\quad (i,j=0,1,\cdots,n)\) 입니다. 이를 decrypt하기 위해선 또다른 secret key가 필요한데, $n\times n$ 크기의 secret key가 필요합니다. 이를 위해서 \(s\otimes s=(s_is_j)_{i,j=1,\cdots,n}\)를 사용할 수 있고, 이 때 \(r_{mul}=b_{0,0}+\sum_{i=1}^{n}(b_{0,i}+b_{i,0})s_i+\sum_{i,j}^{n}b_{i,j}s_is_j\) 이므로 (이는 \(r_{mul}=(a_0+a_1s_1+\cdots+a_ns_n)(a'_0+a'_1s_1+\cdots+a'_ns_n)\equiv rr'\mod{q}\)를 적절히 재배열하면 유도할 수 있습니다) $r_{mul}=rr\mod{q}$를 계산할 수 있습니다. 또한, 여기에 modulo 2를 취하면 $mm’=r_{mul}\mod{2}$가 됩니다. 이 경우에서도 $\lvert rr’\rvert<\frac{1}{2}q$이어야 합니다.

여기에는 두 가지 이슈가 있는데, 첫 번째는 dimension의 증가고, 두 번째는 noise($r$)의 증가입니다. 오직 $O(\log{q})$번의 multiplication만 지원하기 때문에 동작의 한계가 존재합니다. 이를 위해 다음 포스트에서 설명할 linearization이란 방법을 사용하는데, 이는 영완이가 잘 설명할 것이라고 믿습니다. 이는 $n\times n$ secret key로써 만들어지는 ciphertext를 길이 $n$의 secret key를 이용한 ciphertext로 바꾸며, 이를 위해 Linearization gadget($n\times n$ secret key의 encryption)을 활용합니다.

긴 글 읽어주셔서 감사합니다.