cs71107's profile image

cs71107

October 30, 2023 13:00

Introduction

저번 글에서, 이어서, MKHE에 대한 설명을 하겠습니다. 저번 글을 읽고 오시는 것이 이해하기 편할 것 같습니다.

Notation의 경우 저번 글에서 사용한 것을 그대로 가져다가 사용하겠습니다.

이 글에서는 저번 글에서 설명을 다 하지 못한 Multiplication에 대한 설명을 하도록 하겠습니다.

Backgrounds

MKHE의 경우 저번 글에서 기준으로 한 논문에 이어서 추가 연구가 진행됐습니다. 다른 연산의 경우 거의 바뀐 것이 없습니다. 다만, Multiplication의 경우, 현재는 저 논문보다 더 개선된 방식으로 key를 생성해서 evaluation을 수행합니다. 새로 사용하는 방식이 이해도 더 간편하므로, 이 논문에서 기술된 방식을 기준으로 하여 Multiplication을 설명하도록 하겠습니다.

Public Key

위에서 언급한 나중에 나온 논문의 아이디어를 활용하여, 다음과 같은 key들을 public key로 각 party에서 broadcast합니다. security는 기존 RLWE problem에 의해서 보장됩니다. 이때, $\textbf{a}, \textbf{u}$는 CRS로서 공유됩니다.

다음과 같은 key 3개를 사용합시다.

• \[\textbf{ $b_{i}$ } \approx - s_{i} \cdot \textbf{a}\]
• \[\textbf{$d_{i}$} \approx - r_{i} \cdot \textbf{a} + s_{i} \cdot \textbf{g}\]
• \[\textbf{$v_{i}$} \approx - s_{i} \cdot \textbf{u} - r_{i} \cdot \textbf{g}\]

여기서 위의 $\textbf{g}$는 gadget vector입니다.

gadget vector가 뭔지 모르시는 분은 이 글의 gadget decomposition 부분을 참고하시기 바랍니다.

External Product

gadget decomposition으로 decompose된 vector의 상태에서 multiplication을 진행하기 때문에, 이때의 연산은 external product로 부르고, $\boxdot$ 으로 표시합니다.

예를 들어, 어떤 다항식 $c$와, 다항식 vector $\textbf{v}$에 대해,

\[c \boxdot \textbf{v} = \langle \textbf{g}^{-1} (c) , v \rangle (mod \ q)\]

로 표현할 수 있습니다.

vector 쌍 $\textbf{U} = (\textbf{$u_{0}$}, \textbf{$u_{1}$})$에 대해,

\[c \boxdot \textbf{U} = (c \boxdot \textbf{$u_{0}$}, c \boxdot \textbf{$u_{1}$})\]

입니다.

MultiPlication

이제 본격적으로 MKHE를 이해하는데 가장 큰 난관(?)이자 꽃이라고 할 수 있는, MKHE에서 Multiplication을 설명하도록 하겠습니다. 실제 연산을 수행하는 과정에서는 두 ciphertext의 key index set이 다를 수 있지만, 저번 글에서 설명한 방식대로 확장을 해서 같게 만들 수 있으므로, 여기에서는 Multiplication을 하기 전에 두 ciphertext의 key index set이 같고, ciphertext의 각 컴포넌트에 대응되는 key가 같다고 가정하고 설명하도록 하겠습니다.

Tensor

엄밀히 말해서 이 연산을 Tensor라고 부르기로 합의가 된 적은 없지만, 단일 key의 Tensor 연산에 이 연산이 대응된다고 할 수 있으므로, Tensor 연산이라고 하겠습니다.

두 ciphertext $ct_{0}, ct_{1}$를 곱한다고 합시다. $ct_{0} = (c_{0, 0}, c_{0, 1}, \dots, c_{0, k}), ct_{1} = (c_{1, 0}, c_{1, 1}, \dots, c_{1, k})$로 표현될 것입니다.

곱셈에 해당하는 연산을 어떻게 구현할 지 생각해봅시다. $\mu_{0} = c_{0, 0}+c_{0, 1}s_{1}+ \dots + c_{0, k}s_{k}$라고 합시다. 비슷하게 $\mu_{1} = c_{1, 0}+c_{1, 1}s_{1}+ \dots + c_{1, k}s_{k}$라고 합시다. 우리의 목표는, 어떤 $ct = (c_{0}, c_{1}, \dots, c_{k})$가 존재해서, $\mu_{0}\mu_{1} \approx c_{0}+c_{1}s_{1}+ \dots + c_{k}s_{k}$가 성립하는 $ct$를 찾는 것입니다.

지금 당장은 이런 $ct$를 어떻게 찾아야할지 모르겠습니다. 그러니까, 우선 수식을 전개하듯이 생각해봅시다.

\[\mu_{0}\mu_{1} = (c_{0, 0}+c_{0, 1}s_{1}+ \dots + c_{0, k}s_{k})(c_{1, 0}+c_{1, 1}s_{1}+ \dots + c_{1, k}s_{k}) = \sum_{i = 0}^{k}{\sum_{j = 0}^{k}{c_{0, i}c_{1, j} \cdot s_{i}s_{j}}}\]

어떤 2차원 matrix $C$가 존재해서, $C_{ij} = c_{0, i}c_{1, j}$이고, 각 $C_{ij}$에 대해 대응되는 key가 $s_{i}s_{j}$인 2차원 matrix 형태의 ciphertext가 됐습니다.

Relinearization

위처럼 2차원 matrix 형태의 ciphertext를 1차원으로 되돌리지 않고, 계속 연산을 진행하면, 연산을 진행할 때마다 ciphertext의 차원이 계속해서 늘어날 것입니다. 이제 처음 목표대로, 곱셈의 결과에 대응되는 1차원 ciphertext를 찾아봅시다.

편의를 위해서, $c_{ij} = c_{0, i}c_{1, j}$로 표기하겠습니다.

우선, $i = 0$또는 $j = 0$인 경우, $s_{i} = 1$또는 $s_{j} = 1$이므로, 다른 조작을 해줄 필요가 없습니다.

이제 $i > 0, j > 0$인 경우를 생각해봅시다. 우선 $c_{ij}$에 involve 돼있는 key가 $s_{i}, s_{j}$이므로, 어떤 다항식 $f_{0}, f_{i}, f_{j}$에 대해서, $c_{ij} \cdot s_{i}s_{j} \approx f_{0} + f_{i}s_{i} + f_{j}s_{j}$ 가 성립하는 $f_{0}, f_{i}, f_{j}$를 찾아야 합니다. 단순한 수식 계산으로 이런 다항식들을 계산하는 것은 불가능합니다.

단일 key에서 Relinearization을 위해서 Evaluation key를 활용했으니, 우리도 추가적인 key를 활용해서 이 문제를 해결해봅시다.

다음과 같은 식을 생각해봅시다.

\[(c_{ij} \boxdot \textbf{$d_{i}$}) \cdot s_{j} + (c_{ij} \boxdot \textbf{$b_{j}$}) \cdot (\textbf{$v_{i}$} + \textbf{u} \cdot s_{i}\]

바로 뜬금없이 식이 튀어나와서 당황스러울 수도 있지만, 우선 식을 전개해보도록 하겠습니다.

\((c_{ij} \boxdot \textbf{$d_{i}$}) \cdot s_{j} + (c_{ij} \boxdot \textbf{$b_{j}$}) \cdot (\textbf{$v_{i}$} + \textbf{u} \cdot s_{i})\) \(\approx (c_{ij} \boxdot \textbf{$d_{i}$}) \cdot s_{j} - r_{i} \cdot (c_{ij} \boxdot \textbf{$b_{j}$})\) \(\approx (c_{ij} \boxdot \textbf{$d_{i}$}) \cdot s_{j} - r_{i} \cdot (c_{ij} \boxdot \textbf{a})\cdot s_{j}\) \(\approx c_{ij} \cdot s_{i}s_{j}\)

더 detail한 전개는 직접 해보시기 바랍니다.

어쨌든, 위의 식으로 relinearization을 수행할 수 있습니다!!

$(c_{ij} \boxdot \textbf{$d_{i}$}) \cdot s_{j}$ 부분은 $s_{j}$가 곱해져 있는 형태이고, $(c_{ij} \boxdot \textbf{$b_{j}$}) \cdot (\textbf{$v_{i}$} + \textbf{u} \cdot s_{i})$ 부분은 $\textbf{$v_{i}$} + \textbf{u} \cdot s_{i}$ 부분에 주목해서 전개하면 $s_{i}$가 곱해져 있는 부분과 아닌 부분으로 분리할 수 있지요.

따라서, $s_{i}, s_{j}$에 involve 돼있는 부분을 $c_{i}, c_{j}$에 더해주고, 그렇지 않은 부분은 $c_{0}$에 더해주면 됩니다. 모든 $c_{ij}$항에 대해 적절한 항에 더해주는 과정을 마치면, 원하는 $ct$를 얻을 수 있습니다.

Conclusion

이번 글에서는 MKHE 의 Multiplication을 알아보았습니다.

현재에도 MKHE 관련 연구가 활발히 진행되고 있고, Multi - key TFHE 등의 연구도 있으니 관심있는 분들은 찾아보시기 바랍니다. 감사합니다.

Reference

• https://eprint.iacr.org/2019/524
• https://eprint.iacr.org/2021/1412