BGV Scheme (2)

Intro

지난 포스트에서는 BGV scheme의 개념과 기본적인 암호문 연문 (덧셈, 곱셈) 에 대해 설명했습니다. 이번 포스트에서는 BGV scheme의 핵심 개념 중 하나인 ‘Dimension reduction’과 ‘Linearization’에 대해 알아보겠습니다.

Multiplication on BGV

이전 포스트에서 다루었던 BGV에서의 암호문 곱셈을 복기해보겠습니다. 두 ciphertext

\[\mathbf{c}=(a_0, a_1, \cdots, a_n), \mathbf{c'}=(a'_0, a'_1, \cdots, a'_n)\]

에 대해, 두 ciphertext의 tensor product를 계산했습니다.

\[c_{mul}=c\otimes c'=(b_{0, 0}, b_{0, 1}, \cdots, b_{i, j}, \cdots, b_{n, n})\in \mathbb{Z}_q^{(n+1)^2}\] \[(b_{i, j}=a_ia'_j \mod{q}\quad \forall\ 0\le i,j\le 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)=rr'\mod{q}\]

를 유도했습니다. 따라서, $n$ dimension 벡터 $\mathbf{s}$와 $n^2$ dim 벡터 $\mathbf{s}\otimes\mathbf{s}$ 를 secret key로 사용하면 $c_{mul}$을 올바르게 복호화 할 수 있습니다.

Two issues?

이 때 두가지 문제점이 언급되었습니다:

• ciphertext와 secret key의 dimension이 $n$에서 $n^2$으로 증가함 (=> Dimension Reduction)
• 곱셈을 할때마다 noise가 증가함 (=> Noise Reduction)

이 글에서는 첫번째 문제를 다루며, ciphertext와 secret key를 $n$ dimension으로 줄이는 탁월한 아이디어(Linearization)를 기술합니다.

Linearization

$\mathbf{s}\otimes\mathbf{s}$ 로 암호화된 ciphertext를, 동일한 메세지의 $\mathbf{s}$ 로 암호화된 ciphertext로 변환하는 것이 목표입니다. 이를 위해 Linearization Gadget이라는 새로운 벡터를 만들어 줍니다.

Linearization Gadget

Note 편의를 위해 벡터 표기법과 dot product $\cdot$ 를 사용하겠습니다.

Gadget들은 $s\otimes s$ 를 $s$로 암호화한 벡터입니다. 즉 모든 $0\le i,j\le n$에 대해, $s_is_j$를 BGV의 암호화 과정을 따라 암호화합니다.

1. $\mathbf{w_{ij1}} \leftarrow U(\mathbb{Z}^n_q)$ 의 랜덤 벡터와 $e_{ij}\leftarrow D_{\sigma}$ 의 랜덤 노이즈를 생성합니다.

2. $r_{ij} := s_is_j+2e_{ij}$ 에 대해, $w_{ij0} := -\mathbf w_{ij1}\cdot \mathbf s + r_{ij}$ 로 정의합니다. 그러면 암호문 $\mathbf w_{ij}=(w_{ij0}, \mathbf w_{ij1})$ 를 얻을 수 있습니다. 해당 $\mathbf w_{ij}$ 이 Linearization Gadget입니다.

Process

이제 Linearization 과정은 간단합니다. 주어진 Linearization Gadget $\mathbf w_{ij}$와 암호문의 곱 $(b_{ij})_{1\le i,j\le n}$ 에 대해 ($i,j \neq 0$임에 주의), 다음을 계산합니다:

\[c_{lin} := \sum_{1\le i,j\le n} b_{ij} \mathbf w_{ij}\]

$c_{lin}$은 $w_{ij}$의 linear combination 이므로 $(n+1)$ dimension 벡터입니다.

Correctness

이제 motivation을 얻기 위해 $c_{lin}=(c_{lin0}, \mathbf c_{lin1})$을 복호화 해보겠습니다. 복호화는 $(1, \mathbf s)$ 벡터와 내적 연산과 동일합니다. 복호화 연산 (내적)이 linear하다는 것으로부터 다음과 같이 계산됩니다:

\[\begin{split} r_{lin} &= c_{lin0} + \mathbf c_{lin1} \cdot s \\ &= \mathbf c_{lin}\cdot (1, \mathbf s) \\ &= (\sum_{1\le i,j\le n} b_{ij} \mathbf w_{ij}) \cdot (1, \mathbf s) \\ &= \sum_{1\le i,j\le n} b_{ij} [ \mathbf w_{ij} \cdot (1, \mathbf s) ] \\ &= \sum_{1\le i,j\le n} b_{ij} [ w_{ij0} + \mathbf w_{ij1} \cdot \mathbf s\ ] \\ &= \sum_{1\le i,j\le n} b_{ij} r_{ij} = \sum_{1\le i,j\le n} b_{ij} (s_is_j) + 2\left(\sum_{1\le i,j\le n} b_{ij} e_{ij}\right) \end{split}\]

그 결과, 우리가 계산한 $c_{lin}$이 사실은 $\sum_{1\le i,j\le n} b_{i,j}(s_is_j)$ 가 평문이고 노이즈로 $e_{lin} = \sum_{1\le i,j\le n} b_{ij} e_{ij}$ 를 가지는 암호문이라는 것을 확인했습니다.

Better try

이 암호문이 복호화 되려면 노이즈 $e_{lin}$이 modulus 기준 $q$에 비해 작아야합니다. 이를 위해 $b_{ij}$의 비트 표기법을 사용하여 노이즈의 크기를 작게 만드는 방법을 소개하겠습니다.

먼저 lineariation gadget을 모든 $i,j$에 대해 다음과 같이 $k=0,1,2,\cdots,\log q$ 만큼 더 만들어줍니다. 이 때 gadget은 $s_is_j$가 아닌 $2^k s_is_j$를 암호화하여 만들어줍니다:

\[\mathbf w_{ijk}=(w_{ijk0}, \mathbf w_{ijk1})\] \[w_{ijk0} := -\mathbf w_{ijk1}\cdot \mathbf s + r_{ijk}\] \[r_{ijk} := 2^k s_is_j+2e_{ij}\]

이제 linearization process를 $b_{ij}$의 비트 기준으로 수행해줍니다. 이 때 $b_{ijk}$는 $b_{ij}$의 k번째 비트를 나타냅니다.

\[c_{lin} := \sum_{i,j,k} b_{ijk} \mathbf w_{ijk}\]

이 경우 전에 했던것과 동일하게 복호화를 해보면,

\[\begin{split} r_{lin} &= \mathbf c_{lin}\cdot (1, \mathbf s) \\ &= (\sum_{i,j,k} b_{ijk} \mathbf w_{ijk}) \cdot (1, \mathbf s) = \sum_{i,j,k} b_{ijk} [ \mathbf w_{ijk} \cdot (1, \mathbf s) ] \\ &= \sum_{i,j,k} b_{ijk} (2^k s_is_j+2e_{ij}) = \sum_{i,j,k} 2^k b_{ijk} (s_is_j) + 2\sum_{i,j,k} b_{ijk} e_{ij} \\ &= \sum_{1\le i,j\le n} b_{ij} (s_is_j) + 2\left (\sum_{i,j,k} b_{ijk} e_{ij}\right ) \end{split}\]

위와 같이 평문은 여전히 $\sum_{1\le i,j\le n} b_{i,j}(s_is_j)$ 이지만, 노이즈는 $e_{lin} = \sum_{i,j,k} b_{ijk} e_{ijk}$ 로 변한 것을 알 수 있습니다. $b_{ijk}$는 0 또는 1의 값을 가진다는 것을 생각하면 노이즈는 $q$에 비해 충분히 작은 값을 가집니다.

Putting all together

지금까지의 내용들을 총정리 해보겠습니다. BGV에서 두 암호문을 곱하면 둘의 tensor product $c_{mul}$이 나왔습니다.

\[c_{mul}=c\otimes c'=(b_{0, 0}, b_{0, 1}, \cdots, b_{i, j}, \cdots, b_{n, n})\in \mathbb{Z}_q^{(n+1)^2}\]

그리고 우리는 $c_{mul}$을 다음과 같이 복호화해서 $r_{mul}=rr’$, 원래 평문의 곱을 얻을 수 있습니다. \(r_{mul}=rr'=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)\)

하지만 문제는 암호문이 $c\otimes c’$이 되었고, 복호화하는데 $s\otimes s$가 필요하다보니 dimension이 $n^2$으로 증가했습니다. 따라서 linearization을 해줍니다.

Better Try에서 도입한 linearization gadget $\mathbf w_{ijk}$ 를 사용하겠습니다. linearization 과정에서 암호문 $\mathbf c_{lin}$을 얻었고, 이제 최종 암호문 $\mathbf c_{out}$을 다음과 같이 정의해줍니다 (벡터 덧셈에 유의):

\[\mathbf c_{out}=(c_0,c_1,\cdots,c_n)=(b_{0,0}, b_{0,1}+b_{1,0}, \cdots, b_{0,n}+b_{n,0}) + \mathbf c_{lin}\]

Correctness

$c_{out}$을 복호화해서 $r_{out}$을 계산해봅시다.

\[\begin{split} r_{out} &= \mathbf c_{out}\cdot (1, \mathbf s) \\ &= [(b_{0,0}, b_{0,1}+b_{1,0}, \cdots, b_{0,n}+b_{n,0}) + \mathbf c_{lin}] \cdot (1, \mathbf s) \\ &= (b_{0,0}, b_{0,1}+b_{1,0}, \cdots, b_{0,n}+b_{n,0})\cdot (1, \mathbf s) + \mathbf c_{lin} \cdot (1, \mathbf s) \\ &= b_{0,0}+\sum_{i=1}^{n}(b_{0,i}+b_{i,0})s_i + r_{lin} \\ &= b_{0,0}+\sum_{i=1}^{n}(b_{0,i}+b_{i,0})s_i + \sum_{1\le i,j\le n} b_{ij} (s_is_j) + 2e_{lin} \\ &= r_{mul} + 2e_{lin}. \end{split}\]

$r_{mul}=rr’=(m+2e)(m’+2e’)$ 에서 평문만 남기고 $r_{out}$을 정리하면,

\[r_{out}=(m+2e)(m'+2e')+2e_{lin}=mm'+2(me'+m'e+2ee'+e_{lin}) =mm'+2e^*\]

가 됩니다. 즉, 우리가 정의한 $\mathbf c_{out}$은 dimension이 $(n+1)$이면서, 평문 $mm’$와 노이즈 $e^*$를 가집니다. 이것은 우리가 처음부터 목표로 했던 조건입니다! 🚀

Conclusion

BGV scheme의 곱셈 연산에서 발생하는 차원 증가 문제를 해결하는 방법을 살펴보았습니다. 다음 포스트에서는 이 글에서도 언급한 Noise Reduction에 대해 다룰 예정입니다. 감사합니다.