Multi Party Homomorphic Encryption

Introduction

Homomorphic Encryption (HE)는 secret key 가 없어도, ciphertext끼리의 evaluation이 가능한 scheme들으로, cloud computing등에 적합한 model이기 때문에 많은 관심을 받고 있습니다.

Gentry가 처음으로 BGV를 제안안 이후, BFV, CKKS, TFHE 등의 scheme들이 제안됐습니다. 하지만 지금까지 제안되고, 널리 사용되는 scheme들에는 한 가지 공통점이 있는데, 그것은 하나의 고정된 secret key를 가진다는 것입니다.

얼핏 보면 당연할 수 있는 말이지만, 이는 HE scheme들이 가진 단점이기도 합니다. cloud computing 같은 걸 하면 여러 개의 party에 대해 data를 주고 받고, 해야 하는데, 하나의 고정된 secret key에 대해서 연산을 해야 한다면, 연산에 참가하는 모든 party들이 secret key를 알고 있어야 한다는 한계가 생기게 됩니다.

이런 상태라면, malicious party가 있을 때, security를 보장할 수 없고, 만약에 새로운 party가 참가하고 싶다면 secret key를 전해줘야하는 등의 문제가 생기게 됩니다. 이는 여러 모로 HE의 장점과는 반대되는 단점이라고 할 수 있습니다.

이런 문제를 해결하기 위해서, HE는 크게 두 가지 방향으로 발전하게 됩니다.

첫 번째는 Multi Party HE (Threshold) 방식으로, 시작할 때 Party들의 set이 있으면 secret key를 나누어 가지는 (정확히는 살짝 다를 수 있지만, 이해를 돕기 위해 여기서는 이렇게 설명합니다.) 방식입니다. 하나의 secret key에 대해 public key를 생성하여 open하며, 따라서 사실상 key generation 이후에는 하나의 key에 대한 scheme처럼 동작합니다.

두 번째는 Multi Key HE 방식으로, 각각의 Party가 고유의 secret key를 생성하고, 그에 대응되는 public key를 open 합니다. evaluation이 진행됨에 따라서, ciphertext의 길이가 달라지며, decrypt를 하기 위해 ciphertext와 associate된 모든 party의 secret key가 필요합니다.

이 글에서는 https://eprint.iacr.org/2020/304 를 기반으로 해서, Multi Party HE에 대해 설명합니다. (앞으론 MPHE로 쓰겠습니다.)

Backgrounds

참고한 논문은 BFV scheme을 기반으로 하고 있습니다. 이 논문이 BFV scheme인 것이지, 다른 scheme들, 그러니까 CKKS 등의 scheme도 Multi Party HE를 구현하는데 사용될 수 있습니다.

지금까지 5개의 글에 걸쳐 BFV scheme에 관해 설명했으니, 여기서는 알아둬야 할 내용들에 대해서 간단하게만 요약하도록 하겠습니다.

BFV Key Generation

secret key는 $R_3$에서 uniform하게 추출합니다.
public key는 $R_q$에서 $p_1$을 uniform하게 추출하고, error $e$를 discrete gaussian distribution에서 추출합니다. 이때, public key $pk$는, secret key를 $s$라 했을 때, 다음과 같이 표현됩니다. $pk = (p_0, p_1), p_0 = -p_1 \dot s + e$
relinearization key는 $\textbf{r}_1$을 $R_q^l$에서 uniform하게 추출하고, $\textbf{e}$를 $\chi^l$에서 추출했을 때 ($\chi$는 discrete gaussian), secret key $s$에 대해, $rlk = (\textbf{r}_0, \textbf{r}_1) = (s^2\textbf{w}-s\textbf{r}_1+\textbf{e}, \textbf{r}_1)$

BFV Encryption, Decryption

encryption의 경우, message $m$에 대해서, $u$를 $R_3$에서 uniform하게 추출하고, $e_0, e_1$을 $\chi$에서 각각 독립적으로 추출했을 때, $ct = (\Delta m + u p_0 + e_0, u p_1 + e_1)$ 입니다.
decryption의 경우, $ct = (c_0, c_1)$에 대해, $m = [ \lfloor \frac{t}{q} [c_0 + c_1 s]_q \rceil ]_t$ 입니다.

BFV Evaluation

BFV에서는 addition, multiplication을 할 수 있습니다. 자세하게 설명하면 너무 길어지고, 예전 글에서 설명했으므로 넘어가도록 하겠습니다.

더 자세한 내용은 이전에 썼던 글들을 참고해주시면 감사하겠습니다.

개략적인 내용을 원하신다면 이 글을 참고하시기 바랍니다.

CRS

background로 하나 더 언급할 것은, CRS, 즉 Common Random String model 입니다.

CRS model이란 어떤 trusted manner로 random한 string을 생성할 수 있고, 그 string에 모든 party들이 접근할 수 있는 model을 말합니다.

나중에 이유가 나오지만, MPHE는

Scheme Overview

MPHE를 다음과 같은 순서로 설명하겠습니다.

Key Generation
Encryption
Evaluation
Key switching

Key Generation

사실 single-key HE와 가장 많은 차이가 있는 부분입니다.

Ideal Secret Key Generation

먼저, 각각의 party는 BFV에서 secret key를 만들었던 것 처럼, 각각 secret key를 생성합니다. $i$번째 party가 생성한 secret key를 $s_i$라고 합시다.

전체의 secret key $s$는 다음과 같이 정의합니다.

\[s = \sum s_i\]

유의할 것은, 어떤 특정한 storage에 대해 전체 party들에 대한 secret key를 따로 저장하거나 하지는 않습니다. $s$는 어디까지나 이론적으로, 제목처럼 ‘Ideal’하게 존재한다는 것에 유의하시기 바랍니다.

Public Key Generation

public key의 generation을 설명하기에 앞서서, BFV에서 어떻게 public key를 생성했는지 다시 생각해봅시다. secret key $s$에 대해, $R_q$의 $p_1$을 생성한 후, error를 더해서 public key를 생성했습니다.

그러나, 각각의 party에서 각자 public key를 생성하고 더한 것은 public key로 사용할 수 없습니다. 조금만 계산하면 알 수 있습니다.

하지만, 각각의 party가 $p_1$을 공통으로 하고, $p_{0,i} = -s_i p_1 + e_{0,i} $ 와 같은 방법으로, 각자의 secret key $s_i$에 대해 $p_0, i$를 생성하고, $p_0 = \sum p_{0, i}$로 정의하면, $p_0 + p_1 s = \sum e_{0, i}$가 되어, public key 처럼 기능할 수 있게 됩니다.

$p_1$을 공통으로 가질 수 있게 하기 위해서 background에서 언급한 CRS model 설정이 사용됩니다. 현재 CRS model을 사용하기 때문에, $p_1$에 모든 party가 access할 수 있고, 따라서 위의 방식으로 public key를 생성할 수 있게 됩니다.

Relinearization Key Generation

Relinearization Key, 줄여서 $rlk$를 생성하기 위해서는 크게 두 번의 단게를 거쳐야 합니다.

앞서 secret key generation 에서 전체 secret key는 이론적으로, Ideal 하게 존재한다고 설명했습니다. 그런데 $rlk$를 생성하기 위해서는, $s^2$을 처리해야 하기 때문에, 한번으로는 해결할 수 없고, 두 번의 단계를 거쳐야 하는 것입니다.

먼저, CRS로 $R_q^l$에서 uniform하게 추출한 vector $\textbf{a}$와, BFV의 $rlk$의 생성에 쓰였던 decomposition vector $\textbf{w}$가 주어집니다.

각 party들은 첫 번째로 다음과 같은 작업을 합니다.

$i$번째 party는 $R_3$에서 $u_i$를 추출하고, $\chi^l$에서 $\textbf{e}{0,i}, \textbf{e}{1,i}$를 추출합니다. $(h_{0,i}, h_{1,i}) = (-u_i \textbf{a} + s_i \textbf{w} + \textbf{e}{0,i}, s_i \textbf{a} + \textbf{e}{1,i})$ 쌍을 생성합니다.

각 party가 $(h_{0,i}, h_{1,i})$ 쌍을 생성한 뒤, $h_0 = \sum h_{0,i}, h_1 = \sum h_{1,i}$ 을 구합니다.

각 party들은 두 번째로 다음과 같은 작업을 합니다.

$i$번째 party는 $\chi^l$에서 $\textbf{e}{2,i}, \textbf{e}{3,i}$ 를 추출합니다. 이때, $(h’{0,i}, h’{1,i}) = (s_i h_0 + \textbf{e}{2,i}, (u_i - s_i) h_1 + \textbf{e}{3,i})$ 쌍을 생성합니다.

각 party가 $(h’{0,i}, h’{1,i})$ 쌍을 생성한 뒤, $h’0 = \sum h{0,i}, h’1 = \sum h{1,i}$ 을 구합니다.

$rlk = (h’_0 + h’_1, h_1)$ 이 됩니다.

위의 식을 전개해보면 다음과 같습니다.

\[rlk = (\textbf{r}_0, \textbf{r}_1) = (-s \textbf{b} + s^2 \textbf{w} + s \textbf{e}_0 + \textbf{e}_1 + u \textbf{e}_2 + \textbf{e}_3 , \textbf{b})\]

여기에서 $\textbf{e}k = \sum{\textbf{e}{k, i}}$ 이고, $\textbf{b} = s \textbf{a} + \textbf{e}_2$ 입니다.

Encryption

Key Generation이 끝난 후 public key를 얻었으니, single key BFV에서 public key를 통해서 encryption을 할 때와 똑같이 $pk$에 대해서 encryption을 진행하면 됩니다.

Evalutaion

Addition의 경우 다를게 없습니다. single key에서 addition을 할 때처럼 끼리끼리 더해주면 됩니다.

Multiplication 역시, Key Generation이 끝난 후 relinearization key를 얻었으니, single key BFV에서처럼 을 할 때와 똑같이 $rlk$를 사용해서 multiplication을 해주면 됩니다.

Key switching

Key switching은 collective secret key에 대한 정보를 알 수 있을 때 사용할 수 있는 방식, 그렇지 않을 때도 사용할 수 있는 방식 두 가지로 나뉩니다.

Key Switching

각 party가 collective secret key에 대한 정보를 알고 있을 때, 즉 새로운 secret key $s’$에 대해 $i$번째 party가 $s’ = \sum s’_i$인 $s’_i$를 알고 있을 때 사용할 수 있는 방법입니다.

어떤 ciphertext $ct = (c_0, c_1)$이 input이라고 합시다.

$i$번째 party에서는 다음과 같은 $h_i$를 생성합니다.

\[h_i = (s_i - s'_i)c_1 + e_i\]

$h = \sum h_i$라고 하면, 새로운 ciphertext $ct’ = (c_0+h, c_1)$가 됩니다.

Public Key Switching

위의 Key Switching에서 전제하는 조건이 성립하지 않는 상황 (ex. smart contract) 에서는 위의 protocol을 사용할 수 없습니다. 그럴 경우 이 protocol을 사용합니다.

어떤 ciphertext $ct = (c_0, c_1)$과, $pk’ = (p’_0, p’_1)$이 input이라고 합시다.

$i$번째 party에서는 다음과 같은 $(h_{0,i}, h_{1,i})$를 생성합니다.

\[(h_{0,i}, h_{1,i}) = (s_i c_1 + u_i p'_0 + e_{0, i}, u_i p'_1 + e_{1, i})\]

$(h_0, h_1) = (\sum h_{0,i}, \sum h_{1,i})$ 라고 하면, 새로운 ciphertext $ct’ = (c_0 + h_0, h_1)$가 됩니다.

Decryption

decryption은 기본적으로 $s’ = 0$일 때 key switching을 하는 것과 같습니다.

Conclusion

지금까지 MPHE에 대해 간단하게 설명했습니다.

사실 제가 paper에서 분량문제로 의도적으로 생략한 부분이 꽤나 많기 때문에, 더 자세한 내용이 궁금하신 분들은 Reference에도 있는 paper를 직접 읽어보시면 좋을 것 같습니다.

MPHE는 multi party manner로 동작하기는 하나, 사실상 (이론적으로 존재하는) secret key 하나에 대해 동작하는 scheme이라고 볼 수 있기 때문에, noise-growth등에서 detail한 차이는 있지만, single key HE와 거의 비슷하게 동작합니다. 이는 위의 설명 글에서도 쉽게 확인할 수 있을 것입니다.

그렇기 때문에, MPHE는 속도가 빠른 편입니다. 반면, 다른 갈래 중 하나인 MKHE는 ciphertext 자체의 길이가 늘어나기 때문에, MPHE에 비해서 느리게 동작합니다.

하지만, MPHE가 가지는 한계점도 있습니다. 처음에 Key Generation을 할 때, Evaluation에 참여하는 모든 party가 정해져 있다는 것입니다. 만약에 새로운 party가 join을 해야 한다면, 다시 key setting을 해야 하죠. 따라서 flexibity가 떨어진다는 것이 단점이라고 할 수 있습니다.

반면, MKHE의 경우에는 이런 점으로 부터 자유롭습니다.

사실 이 글이 기반으로 하고 있는 paper 뒤에도 연구가 계속 진행돼서, 현재 최신 연구들에서는 $rlk$등을 여기에서 설명한 방식으로 생성하고 있지는 않습니다.

하지만 MPHE (Threshold HE)의 발전을 이해하는데 필요한 논문인 것 같으니, 읽어보시고 이해하는 것을 추천드립니다.

저는 다음에 또 다른 주제로 돌아오도록 하겠습니다. 부족한 글 읽어주셔서 감사합니다.

Reference

https://eprint.iacr.org/2020/304
https://crypto.stackexchange.com/questions/58558/what-is-the-common-reference-string-crs-model