Flexible Threshold Fully Homomorphic Encryption and its Decentralization via Key Generation Protocol

Abstract

Eurocrypt 2012 에서 Asharov 등은 learning with errors (LWE) 문제를 기반으로 하여 $(n,n)$-정족수 완전동형암호를 제안하였다. 이 스킴은 n 개의 참여자들 간에 수직적인 상하구조가 없도록 탈중앙화 동형암호를 설계하였으며 이때 복호화는 구성원의 참여자들이 모두 만장일치로 동의해야만 한다. 하지만 이러한 사실은 다양한 활용 예를 고려해 봤을 때 현실적인 어려움을 주기에 보다 일반적인 정족수 완전동형암호에 대한 연구가 요구되었다.

최근 Crypto 2018에서는 Boneh 등이 Shamir 비밀 공유 스킴과 {0,1}-선형 비밀 공유 스킴을 활용하여 두 가지의 일반적인 정족수 완전동형암호를 제안하였다. 하지만 그들의 방법은 $O(n^{4.2})$ 개의 비밀키를 저장해야 하거나 혹은 굉장히 큰 modulus space 를 필요로 하기 때문에 현실적인 적용에는 아직 비효율적이라고 할 수 있다.

본 논문에서는 효율적인 정족수 완전동형암호의 설계를 위해 Inhomogeneous Small Integer Solution (ISIS) 문제를 활용하여 격자기반 암호에 특화된 정족수 스킴을 제안한다. 기본적인 아이디어는 기존의 역치값 $t$ 를 그 역할에 따라 안전성을 위한 $t_s$와 정확성을 위한 $t_c$로 구분하는 것으로부터 시작되었다. 그 결과, 우리는 기존 정족수 스킴이 일반화된 가변적인 정족수 스킴을 설계하고 결과적으로 가변적인 정족수 완전동형암호를 얻을 수 있었다. 이 새로운 정족수 완전동형암호는 고정된 modulus 크기를 기준으로 기존 대비 훨씬 많은 구성원에 대해 적용이 가능하다. 더 나아가, 본 논문에서는 $(t,n)$-정족수 스킴으로부터 공유 비밀값이 $n$배되는 것을 대가로 $(2t, 2n)$-정족수 스킴을 만들어내는 일반적인 방법을 소개한다.

두번째로, 본 논문에서는 Shamir의 비밀 공유 스킴을 활용해 공유 비밀값을 갱신하는 방법을 소개하고 이를 통해 탈중앙화 정족수 완전동형암호를 설계하고 최적화를 진행한다. 이 방법은 보다 일반적으로 적용할 수 있으나 여기에서는 천정희 교수 외 3인이 설계한 HEAAN 동형암호를 중심으로 서술하기로 한다.

In Eurocrypt 2012, Asharov et. al. presented an $(n,n)$-threshold fully homomorphic encryption (threshold FHE) scheme based on learning with errors (LWE) problem. The scheme is decentralized in the sense that there is no hierarchy among $n$ parties, and the decryption can be carried out only with the unanimous approval. They also constructed a three round multiparty computation (MPC) protocol where all $n$ parties should be online through the protocol, which is not desirable for practical applications. They also give a $(n,n)$-threshold FHE scheme based on ring LWE problem which requires one more round to construct a MPC protocol, namely four round.

In most recent work given by Boneh et al, two constructions of general $(t, n)$-threshold FHE with non-interactive decryption protocol are suggested based on $\{0,1\}$-Linear Secret Sharing Scheme (LSSS), whose recovery coefficients are just 0 or 1, or Shamir secret sharing scheme. In their constructions, they require the recovery coefficients of LSSS to be sufficiently small so that it can guarantee the correctness of decryption. As an extreme case, they adapted $\{0,1\}$-LSSS which provides \textit{compactness} property while the number of secret shares for each party becomes $O(n^{4.2})$ causing a significant space overhead. On the other hand, to use the Shamir secret sharing scheme, they enlarge the bitsize of modulus space with factor $O(n \text{log} n)$ so that the recovery coefficients after clearing the denominators are still small relative to modulus $q$.

In this thesis,

1. We develop a new threshold scheme for lattice cryptographies by using Inhomogeneous Small Integer Solution (ISIS) problem. We begin with separating the threshold bound $t$ into a bound for security and a bound for correctness. As a result, we construct a \textit{flexible threshold scheme} which is a relaxation of threshold scheme, and then derive a \textit{flexible threshold fully homomorphic encryption}. This new threshold FHE supports much larger the number of parties $n$ than those of previous works for a fixed modulus of ciphertext with $O(1)$ shares. Moreover, we provide a generic method for making $(2t, 2n)$-threshold scheme from $(t, n)$-threshold scheme with $n$ times the number of secret shares. For the ordinary secret sharing, we can make security and correctness bounds to be same by combining our flexible threshold FHE and generic method. It gives new threshold FHE which supports larger threshold bound $t$ and number of parties $n$ than the previous works.

2. We construct a \emph{decentralized} $(t,n)$-threshold FHE scheme in which at least $t$ parties can decrypt the ciphertexts, for any $t\leq n$. To do this, we introduce how to update secret key shares for $(t,n)$-threshold functionality by using Shamir's secret sharing scheme. Especially, we instantiate our $(t,n)$-threshold FHE scheme focusing on HEAAN FHE scheme by Cheon \et. Our MPC protocol is still more advantageous in the sense that it works even when at least $t$ parties among $n$ parties are online. To get a smaller error, we further modify the evaluation key generation.