BGV Scheme (3)

Linearization, and more

Linearization이란 BGV Scheme에서 multiplication에서 발생하는 차원 증가 문제에 대한 방안이었습니다. 한편, multiplication엔 한 가지의 문제가 더 있습니다. 바로 noise의 증가입니다. Linearization 자체에서 발생하는 큰 노이즈 증가의 문제는 better try를 통해 $\log{q}$에 bound될 수 있었지만, 문제는 Multiplication과 Linearization을 같이 진행하면 다음 procedure에 따라 결과적으로 rough하게 $r^2$에 bound된단 사실을 알 수 있습니다.

input ciphertext $c=(a_0, a_1, \cdots, a_n), c’=(a’_0, a’_1, \cdots, a’_n)$을 정의합시다. 이 때 $a_0+a_1s_1+\cdots+a_ns_n\equiv r\mod q, \quad a’_0+a’_1s_1+\cdots+a’_ns_n\equiv r’\mod q$ 입니다.

• Step 1: $c_{mul}=c\oplus c’=(b_{0, 0}, b_{0, 1}, \cdots, b_{i, j}, \cdots, b_{n, n})\in Z_q^{(n+1)^2}$을 계산합시다.
• Step 2: Linearization gadget $W$에 대해 $c_{mul}$에 $W$를 이용하여 Linearization을 수행하고, 그 결과를 $c_{lin}=(c_0, c_1, \cdots, c_n)$이라고 합시다.
• Step 3: 이를 정리하면 이전 글의 결론에 의하여 $r_{lin}=c_0+c_1s_1+\cdots+c_ns_n,\quad r_{lin}=rr’+2e_{lin}$이 됩니다. 이를 이용하여 정당성을 증명할 수 있으며, homomorphic함을 보일 수 있습니다.

한편, 이 때 noise growth를 관찰해 봅시다. modulus $q$이고 noise $B$인 input ciphertext들이 있다고 가정합시다. 이 때, computation의 level과 degree를 다음과 같이 정의합니다: multiplication을 수행하는 ciphertext들의 개수를 degree로, computation level $L$은 degree $2^L$로 정의해 봅시다. 이 때, 다음과 같은 성질이 성립합니다.

• input ciphertext는 noise $r\approx B$입니다.
• Level 1 (degree 2) computation의 경우, noise magnitude $r\approx B^2$입니다.

• Level 2 (degree 4) computation의 경우, noise magnitude $r\approx B^4$입니다.

  $\vdots$

• Level L (degree $2^L$) computation의 경우, noise magnitude $r\approx B^{2^L}$입니다.

하지만, $|r|< \frac{1}{2}q$이어야 올바른 decryption이 이루어집니다. 어떻게 해야 할까요?

Noise Reduction

이제 BGV Scheme의 첫 번째 글에서 언급했던 두 가지 문제 중 마지막 문제, noise의 증가에 대한 문제에 대한 해답을 얻을 차례입니다. 이를 부분적으로 해결하기 위하여, modulus switching이란 아이디어를 사용해 봅시다. 주어진 암호문 $c=(a_0, a_1, \cdots, a_n)\in \mathbb{Z}_q^{n+1}$에 대하여 $a_0+a_1s_1+\cdots+a_ns_n\equiv r\mod{q}, \quad r=m+2e$라고 정의해 봅시다. 이 때 암호문 $c$ 전체를 특정 조건에서 어느 정도 scale해 보는 것이 핵심 전략이 됩니다. 정확히는, $p<q$에 대하여 암호문 전체에 $p/q$를 곱한 뒤 특정 조건에서 round한다는 것인데, 더 자세하게 알아봅시다.

암호문 $c$가 주어지면, 다음과 같은 암호문 \(c'=(a'_0, a'_1, \cdots, a'_n)\in \mathbb{Z}_{p}^{n+1}\)을 찾아 봅시다:

• 조건 1: $a’_i\approx (p/q)\times a_i$
• 조건 2: $a’_i\equiv a_i\mod{2}$

이 때, secret key $\mathbf{s}$의 $\mathcal{l}_1(\mathbf{s})$가 충분히 작아야 한다는 조건이 필요합니다. ($\mathcal{l}_1(\mathbf{s})$는 $\mathbf{s}$의 $\mathcal{l}_1$ norm을 의미합니다.)

이제, 한 가지 주장을 하려고 합니다. $r’\in \mathbb{Z}$인 $r’$에 대해 $a_0+a_1s_1+\cdots+a_ns_n\equiv r’\mod{q}$가 성립함의 내용인데, 이 때 $r’$에 대해 $r’\equiv r\mod{2}$가 성립합니다.

그러므로, 어떤 $e’\approx (p/q)\times e$에 대해 $r’=m+2e’$가 성립합니다.

이를 다시 한 번 정리하면, $r’\approx (p/q)\times r$이며 $r’\equiv r\mod 2$인 $r’$에 대해 $a’_0+a’_1s_1+\cdots+a’_ns_n\equiv r’\mod{p}$가 성립함이라고 이야기할 수 있습니다. 즉, $m=0 \text{ or } 1$에 대해 $c$를 $c’$으로 대체하면 $r$은 $r’$으로 바뀌게 되지만, decrypt 과정의 결과물인 $m$은 변하지 않는다는 결론입니다. 어떻게 이런 내용이 성립할까요? 이를 알아보기 전에, 말하지 않은 조건이 한 가지 더 있습니다. 바로, $|r|<q/2-(q/p)\times \mathcal{l}_1(\mathbf{s})$라는 조건입니다. (위에서 \(\mathcal{l}_1(\mathbf{s})\)가 작아야 한다고 언급했던 것이 이 때문입니다) 그러면, 증명을 함께 알아봅시다.

Proof. $a_0+a_1s_1+\cdots+a_ns_n=r+qK$라고 놓아 봅시다. 동일한 $K$에 대해, $e_p=a’_0+a’_1s_1+\cdots+a’_ns_n - pK\in\mathbb{Z}$라고 놓아 봅시다. 이 때, 임의의 $i$에 대해 $a_i=a’_i\mod 2$이고 $p=q\mod 2$ 이므로 $e_p=r\mod 2$라고 둘 수 있습니다. 즉, 원래 증명하고자 했던 것을 증명하기 위해서는 $e_p=r’\mod 2$임을 증명하면 됩니다. 이 식을 변형하면, $e_p=r’=(p/q)r+(r’-(p/q)r)$이 됩니다. 이런 형태의 식으로부터 위에서 새롭게 추가한 조건을 응용할 수 있는데, 위의 조건에 $p/q$를 곱한 뒤, $e_p$와 같이 정리해 봅시다. 그러면 $|e_p|\le (p/q)r+\mathcal{l}_1(\mathbb{s})<p/2$가 나오게 되고, 이는 $e_p=r’$을 의미합니다. 즉, $r=r’\mod 2$이고, 증명이 완료됩니다.

눈치 빠른 분들은 알아채셨겠지만, 하나 더 알 수 있는 사실이 있습니다. 바로, $r’$이 줄어든다는 사실인데, 이를 통해 더 강력한 최적화를 통해 bootstrapping이라 부르는 기술 없이도 SHE를 FHE로 바꿀 수 있다고 합니다. 이 글에서는 더 자세히는 다루지 않습니다.

Modulus Chain and Noise Growth

Modulus Chain이라 부르는 것은, modulus switching 과정에서 바뀌는 $q$에 대해 초기의 $q$ 값을 $B^{L+1}$로 설정했을 때 $L$이 modulus switch 가능한 maximal level을 나타내고, 이를 통해 chain을 만들 수 있음을 의미합니다. 더 자세히 서술하면 다음과 같습니다.

modulus $q_{L}=B^{L+1}, \quad |r|\approx B$인 input ciphertext라고 가정합니다.

1. level 1 (degree $2$) computation의 경우, noise magnitude는 $B^2$가 됩니다.
   • $q_{L-1}=q_{L}/B$로 modulus switching을 거친 뒤에, noise magnitude는 $B$가 됩니다.
2. level 2 (degree $2^2$) computation의 경우, noise magnitude는 $B^2$가 됩니다.
   • $q_{L-2}=q_{L-1}/B$로 modulus switching을 거친 뒤에, noise magnitude는 $B$가 됩니다.

   $\vdots$

3. level L (degree $2^L$) computation의 경우, noise magnitude는 $B^2$가 됩니다.
   • $q_{0}=q_{1}/B$로 modulus switching을 거친 뒤에, noise magnitude는 $B$가 됩니다.

$q_0=B$에 도달한 이후, 더 이상 multiplication을 진행할 수 없게 됩니다. 이 때, \(q_0\text{ }\vert \text{ }q_1\text{ }\vert\text{ }\cdots \text{ }\vert\text{ }q_L=B^{L+1}\)을 modulus chain이라고 합니다.

What changed if applied Modulus Switching?

Modulus Switching을 적용하게 된다면, Level $L$에 대해 기존의 경우 condition이 초기 $q>B^{2^L}$이었던 것에 비해 condition이 초기 $q>B^L$로 작아지게 됩니다. 이는 큰 변화이며, 이를 잘 발전시키면 앞에서 언급한 bootstrapping을 대체하는 것이 가능하게 됩니다.

Generalization and Optimization

이 글에서는 여기에 대해 엄밀하게 다루진 않고, 간략한 outline만 소개합니다. 우선, 앞에서 $2$로 다뤘던 두 번째 modulus에 대해 이를 $p$로 확장할 수 있습니다. 이를 수학적으로 표현하면 다음과 같습니다.

임의의 소수 $p$에 대해, $r=pe+m$에 대해 $a_0+(a_1s_1+\cdots+a_ns_n)=r\mod{q}$를 만족시키는 $a_0, \cdots, a_n$에 대해 $\mathbf{c}=(a_0, a_1, \cdots, a_n)\in\mathbb{Z}^{n+1}_{q}$를 만족.

또한, packing technique라는 기술이 존재합니다. 이는, message가 $m$ 하나로 고정되는 것에 그치지 않고 이를 $n$개의 message space로 확장하는 것을 의미합니다. 수학적으로는, message를 $\mathbb{Z}_q$에서 $\mathbb{Z}^n_q$로 확장하는 것을 의미합니다. 실제로 이렇게 message space를 확장하여도 ciphertext의 크기는 그렇게 커지지는 않는다고 합니다. ($2$배씩 커진다는 결과가 있습니다) 또한, 이는 SIMD의 방식으로 vectorized 연산을 지원하는데, 다음과 같이 덧셈과 곱셈 연산을 지원합니다.

• $E(\mathbf{s}, \mathbf{m})+E(\mathbf{s}, \mathbf{m’})=E(\mathbf{s}, \mathbf{m+m’})$, for $\mathbf{m+m’}=(m_1+m’_1, m_2+m’_2, \cdots, m_n+m’_n)$
• $E(\mathbf{s}, \mathbf{m})\times E(\mathbf{s}, \mathbf{m’})=E(\mathbf{s}, \mathbf{m\times m’})$, for $\mathbf{m\times m’}=(m_1\times m’_1, m_2\times m’_2, \cdots, m_n\times m’_n)$

이러한 연산을 통해, 더 나은 amortized complexity가 제공되게 됩니다.

Bootstrapping

현재까지 알아본 BGV는 SHE에 속합니다: depth가 깊어질수록, circuit을 제대로 evalute할 수 없기 때문입니다. 이에 대한 방법이 Gentry의 Bootstrapping입니다. 물론 noise 자체를 없애는 건 쉽습니다. (또는 ciphertext의 level을 recover하거나) 바로, 그냥 암호문을 decrypt하고 다시 encrypt하면 됩니다. 하지만, secret key 없이 이를 수행할 수 있을까요?

$\mathbf{c}$를 $m\in{0,1}$에서의 encryption이라고 가정합시다. 다르게 말하면, $\mathrm{Dec}(\mathbf{s}, \mathbf{c})=m$이 됩니다. 이제, 새로운 함수 $F$를 정의하는데, 이는 secret key를 input으로 갖는 함수입니다. 즉, 이를 다시 쓰면 $F(\mathbf{s})=F(s_1, \cdots, s_n)=m$인 함수가 되고, 이는 ${0,1}^n\rightarrow {0,1}$인 함수가 됩니다.

이제, 앞서 설명한 Linearization gadget과 비슷한 것을 만들어주도록 하겠습니다(이를 relinearization Gadget이라고 하는 것 같습니다). \(\mathbf{s'}=(s'_1, \cdots, s'_n)\)을 그러한 벡터라고 해 봅시다. 이 때, Bootstrapping key라고 부르는 벡터를 만들어 봅시다. Bootstrapping key \(\mathbf{BK}=\{\mathbf{k_i}=E(\mathbf{s'}, s_i)\}_{1\le i\le n}\)는 다른 말로, 원래 secret key \(\mathbf{s}\)의 각 \(s_1, s_2, \cdots, s_n\)을 secret key \(\mathbf{s'}\)에 대해 암호화한 것을 말합니다. (이는 $n\times n$ 벡터가 됩니다) 그러면, 다음과 같은 식이 성립하게 됩니다.

\[F(\mathbf{k_1, k_2, \cdots, k_n})=F(E(\mathbf{s'}, s_1), \cdots, E(\mathbf{s'}, s_n))=E(\mathbf{s'}, F(s_1, \cdots, s_n))=E(\mathbf{s'}, m)\]

이는 함수 $\mathrm{Enc}$와 $\mathrm{Dec}$의 homomorphic한 성질에 의해 보존되는 성질입니다. 정확히는, 함수 연산 자체에 대해서도 암호화와 복호화는 homomorphic하므로, 위와 같은 등식이 성립하게 됩니다.

다시 정리하면, bootstrapping은 다음과 같은 과정을 거쳐 이루어집니다.

• Setup
  • 새로운 secret key $\mathbf{s’}\in {0,1}^n$을 생성
  • Bootstrapping key $\mathbf{BK}={\mathbf{k_i}=E(\mathbf{s’}, s_i)}_{1\le i\le n}$ 생성
• Boostrapping Procedure

  • Input: ciphertext $\mathbf{c}$ under $\mathbf{s}$와 bootstrapping key $\mathbf{BK}={\mathbf{k_i}=E(\mathbf{s’}, s_i)}_{1\le i\le n}$

  • 위에서 정의한 대로 $F$를 정의하고, $\mathbf{c’}=F(\mathbf{k_1, k_2, \cdots, k_n})$을 계산한 뒤 $\mathbf{c’}$을 output합니다.

• Correctness
  • $\mathbf{c’}$은 $s’$에서 $m$의 encryption이 됩니다. $\rightarrow$ 위에서 보였습니다.
  • $\mathbf{c’}$의 level은 어떻게 될까요? 이는 함수 $F$가 동작하는 데 얼마만큼의 level이 줄어드는지에 따라 달려 있습니다. 이를 $d$라고 하면, 남은 level $\mathcal{l}=L-d$라고 정의할 수 있습니다. 즉, $L>d$일 때 BGV Scheme이 bootstrappable하다고 합니다.

일반적으로 $\mathbf{s’}=\mathbf{s}$로 정해 계속해서 circular한 구조를 반복하게 해 bootstrapping을 반복하게 한다고 합니다. 하지만, 여기에는 한 가지 문제가 있습니다. 아직까지 open question이라고 하는데, secret key $\mathbf{s}$로 만들어진 $\mathbf{s’}$가 random string과 indistinguishable하단 증명이 없다고 합니다.

이상입니다. 긴 글 읽어주셔서 감사합니다. 다음에는 CKKS Scheme으로 찾아뵙겠습니다.