Multi Key Homomorphic Encryption - 2

cryptography

Introduction

저번 글에서, 이어서, 이 논문의 내용을 기준으로 하여, MKHE에 대한 설명을 이어서 진행합니다. 따라서, 저번 글을 읽고 오시는 것이 여러 면에서 도움이 됩니다.

아래에 정리해둔 Notation에 잘 모르겠다는 부분이 있다면, 저번 글과 BFV를 설명한 글들을 읽고 오시는 것을 추천드립니다.

Backgrounds

Notation

이 글에서는 논문에서 사용한 Notation을 거의 따릅니다. 저번 글에도 썼지만, 다시 정리하면 다음과 같습니다.

먼저, $\textbf{u}, \textbf{v}$처럼 굵은 소문자들은 vector를 나타냅니다.
그리고, $\langle \textbf{u} , \textbf{v} \rangle$는 vector의 innner product를 나타냅니다.
real number $r$에 대해, $\lfloor r \rceil$은 가장 가까운 integer를 가리킵니다.
$x \leftarrow D$는 distribution $D$에 따라 $x$를 추출했음을 나타냅니다.
finite set $S$에 대해서, $U(S)$는 $S$의 각 원소를 uniform하게 추출하는 분포를 나타냅니다.
미리 정해진 $n$은 power of 2로써, $R = \mathbb{Z} [ X ] / (X^{n} + 1)$ 입니다.
$R_q = R / (q \cdot R)$ 입니다.
$\chi$는 $R_q$위의 secret key를 추출하는 distribution입니다.
$\psi$는 $R$위의 error를 추출하는 distribution입니다.
$d$는 gadget decomposition에 의해 decompose될 때, gadget vector의 차원입니다.
$i$번째 party의 secret key는 $s_i$, public key는 $pk_i = (p_{0,i}, p_{1,i})$로 표시합니다.

Operations

이제 본격적으로, MKHE의 operation들에 대해서 알아봅시다.

Encoding, Decoding

Encoding, Decoding은 MKHE라고 해서 크게 달라지지 않습니다. 따라서 생략합니다.

Encryption

기본적으로 어떤 하나의 encrypt 연산의 결과로 생긴 ciphertext를 보통 fresh 하다고 많이 표현합니다.

fresh ciphertext를 생각하면, 보통 어떤 party의 public key (pk)를 사용해서 encrypt를 하게 됩니다. 이렇게 encrypt를 할 때에는, single key encryption 처럼, 두 개의 polynomial로 구성됩니다.

예를 들면, $ct = (c_0, c_1)$ 같은 형태가 될 것입니다. $i$번째 party의 key를 사용했다면, $c_0 + s_{i} c_{1}$를 하면 message에 관련된 정보를 얻을 수 있을 것입니다.

저번 글에도 MKHE의 process라는 이름으로 간단하게 설명했습니다만, 이제 여러 개의 party에서 encrypted 된 message를 evaluate하고 싶을 때, ciphertext의 형태가 어떻게 변화하는지 좀 더 formal하게 살펴봅시다.

어떤 Evaluation Circuit $C$에 대해서, ciphertext $ct_1, ct_2, \dots , ct_n$에 대해 연산을 진행한다고 합시다. ciphertext $ct_i$는 $j_{i}$번째 party의 key를 사용하여 encrypted된 fresh ciphertext라고 합시다. 그럼 ciphertext의 형태들은 다항식의 pair들이 될 것입니다. 이제, $C$를 적용한 결과 $ct = C(ct_{1} , ct_{2} , \dots , ct_{n})$를 생각하면, $ct$도 여전히 다항식의 pair 형태일까요?

단순히 더하기만 하는 형태의 Circuit이 아니라, 여러 가지 복잡한 연산이 들어가는 Circuit이면, public key들만을 사용해서 조정할 수 있으니 목표를 달성하기가 매우 어려워 보입니다. 이런 상황에서, MKHE는 ciphertext의 크기를 ‘늘리는’ 선택을 합니다. 좀 더 formal 하게 설명하자면, index들의 set $I = { j_{i} }$에 대해, $I$의 크기를 $m$이라고 합시다. 그러면 $ct$는 다음과 같이 $m+1$개의 다항식 tuple이 됩니다. 수식으로 표현하면 다음과 같습니다.

\[ct = (c_{0}^{\ast}, c_{1}^{\ast}, \dots c_{m}^{\ast})\]

fresh한 ciphretext $ct_i$들을 $ct$와 같은 형태로 확장시킨 형태를 $ct^{\ast}_i$라고 합시다.

\[ct^{\ast}_i = (c_{0, i}^{\ast}, c_{1, i}^{\ast}, \dots c_{m, i}^{\ast})\]

원래 $ct_{i}$는 $ct_{i} = (c_{0, i}, c_{1, i})$ 와 같이 표현된다고 합시다. 그럼, $c_{0, i}^{\ast} = c_{0, i}$ 이고, 어떤 $k$에 대해 $c_{k}^{\ast}$와 match되는 key가 $s_{i}$라고 하면, $c_{k, i}^{\ast} = c_{1, i}$이고, 그 외의 $c_{j, i}^{\ast} = 0$ 으로 두면 확장이 됩니다.

앞으로는 구현등에 따라 달라질 수 있기 때문에 생략하겠지만, 기본적으로 이런 방식으로 확장을 한 후 연산들을 한다고 생각하면 됩니다.

그리고, 저렇게 나온 $ct$에 대해 index set $I$를 $ct$에 involved된 index들의 집합이라고 합니다.

Decryption

Decryption을 위해서는 당연히 secret key가 필요합니다.

Decryption을 할 ciphertext $ct = (c_{0}, c_{1}, \dots , c_{m})$ 를 decrypt 하기 위해서는, $1 \le i$인 $i$에 대해, 각 $c_{i}$에 대응되는 secret key를 가지고 있는 party가 $j$번째 party라고 하면, $c_{i} s_{j}$를 계산해주어야 합니다. 그리고 계산된 값들을 전부 합하면, message에 대한 정보를 얻을 수 있습니다.

Addition

각 component 끼리 더해주면 됩니다.

즉, $ct = ct_{1}+ct_{2}$라고 합시다. $ct = (c_{0}, c_{1}, \dots c_{n}), ct_{1} = (c_{1, 0}, c_{1, 1}, \dots c_{1, n}), ct_{2} = (c_{2, 0}, c_{2, 1}, \dots c_{2, n})$

Multiplication

key 생성등이 복잡한편이라, 나중에 따로 서술하도록 하겠습니다.

Conclusion

이번 글에서는 MKHE 의 각 연산을 알아보았습니다. 단, Multiplication의 경우, 시간부족으로 인해서, 다음 글에서, 대신 좀 더 자세하게 설명하게 될 것 같습니다.

현재 HE는 Secured ML 등 다양한 분야에서 주목 받고 있지만, 대부분의 Application의 경우 Single key HE로만 구현돼있는 것이 대부분입니다. Multi-Key based HE를 바탕으로 된 구현은 거의 없다고 봐도 됩니다.

그럼에도, Multi-Key를 바탕으로 한 HE의 구성이 분명한 의미가 있기 때문에, 아직도 많은 연구가 이루어지고 있습니다.

참고로, CDKS는 2019 CCS에 제안된 것이고, 현재는 이 scheme에서 더 나아간 state-of-art의 scheme들이 나와 있습니다. 관심 있는 분들은 찾아봐도 좋을 것입니다.

Reference

https://eprint.iacr.org/2019/524