A Unified Framework of Homomorphic Encryption for Multiple Parties with Non-Interactive Setup

Abstract

동형암호(Homomorphic Encryption)는 암호화된 상태에서 복호화 없이 연산을 가능하게 하는 암호 체계입니다. 일반적인 동형암호는 같은 키로 암호화된 암호문에 대해서만 연산을 지원하기 때문에, 여러 참여자가 있는 경우 권한이 (단일) 비밀 키를 소유한 참여자에게 집중되는 문제가 있습니다. 이 문제를 해결하기 위해 두 가지 다른 동형암호 스킴인 다자간 동형 암호(Multi-Party Homomorphic Encryption)와 다중키 동형암호(Multi-Key Homomorphic Encryption)가 개발되었습니다. 다자간 동형암호는 효율적이지만 키 생성 시 참여자 간 상호 작용이 필요하며, 참여자 집합이 고정되어야 합니다. 반면, 다중키 동형암호는 참여자 수에 비례하여 성능이 저하되지만, 연산 중간에 새로운 참여자를 추가할 수 있는 장점이 있습니다. 본 연구에서는 비대화식 키 생성을 가지는 첫 번째 다자간 동형암호를 제안합니다. 제시한 다자간 동형암호는 재선형화 키가 비밀 키에 대해 선형적이기 때문에 참여자들이 생성한 키들의 합산으로 계산될 수 있습니다. 이로 인해 각 참여자가 상호작용 없이 독립적으로 키를 생성할 수 있습니다. 또한 새로운 동형암호 스킴인 그룹간 동형암호 (Multi-Group Homomorphic Encryption) 를 제안합니다. 그룹간 동형암호는 다자간 동형암호와 다중키 동형암호를 통합한 스킴으로, 이 두 가지의 장점을 모두 가집니다. 그룹간 동형암호에서는 각 참여자 그룹이 다자간 동형암호와 같이 공동 키를 생성하여 데이터를 암호화하고, 그룹 안에서 연산을 하는 경우 다자간 동형암호와 같이 동작합니다. 그러나 그룹 간 연산을 수행할 때에는 다중키 동형암호와 같이 연산하여 새로운 그룹이 연산에 참여할 수 있습니다. 마지막으로, 제안한 그룹간 동형암호를 이용하여 다자간 연산 프로토콜을 구축하고 그 안전성을 검증합니다. 또한 그룹간 동형암호를 이용하여 다자간 동형암호와 같이 학습을 수행하고 다중키 동형암호와 같이 추론을 수행하는 로지스틱 회귀 모델을 제시합니다.

Homomorphic Encryption (HE), first demonstrated in 2009, is a class of encryption schemes that enables computation over encrypted data. The standard HE, however, poses an authority issue when multiple parties are involved, as the authority is concentrated solely to whom that owns the (single) secret key. To solve this issue, variants of HE have emerged in the context of multiple parties, resulting in the development of two different lines of HE schemes – Multi-Party HE (MPHE) and Multi-Key HE (MKHE). MPHE schemes tend to be much more efficient; but require the interaction between parties in the key generation and the set of parties is fixed throughout the entire evaluation. On the other hand, MKHE schemes have poor scaling with the number of parties but allow us to add new parties to the joint computation anytime. In this work, we construct the first MPHE scheme that features a non-interactive key generation. We refactor the evaluation key to be nearly linear, allowing it to be computed by simple summation. As a result, our MPHE allows each party to independently and asynchronously broadcasts its key. In addition, we propose a new HE primitive, called Multi-Group HE (MGHE). Stated informally, an MGHE scheme provides seamless integration between MPHE and MKHE, and combines the best of both these primitives. In an MGHE scheme, a group of parties generates a public key jointly which results in compact ciphertexts and efficient homomorphic operations, similar to MPHE. However, unlike MPHE, it also supports computations on encrypted data under different keys, a property enjoyed by MKHE schemes. We present a construction of MGHE from the BFV scheme and provide a proof-of-concept implementation to demonstrate its concrete performance. Finally, we describe a general approach to construct a multi-party protocol from MGHE. We provide a proof-of-concept implementation of a logistic regression model where our MGHE interpolates between MPHE (where the training is performed) and MKHE (where the inference is performed).