Multi-key Homomorphic Encryption with Threshold Re-encryption

Multi-key Homomorphic Encryption with Threshold Re-encryption

연구 분야: Cryptography

학회: International Conference on Selected Areas in Cryptography

Fully homomorphic encryption (FHE) is a cryptographic scheme that allows users to perform arbitrary arithmetic operations over plaintexts by operations (called homomorphic operations) on ciphertexts without decryption. A multi-key FHE (MK-FHE) can perform homomorphic operations on ciphertexts encrypted with different encryption keys. In MK-FHE schemes, to decrypt a ciphertext encrypted with different users’ keys, users having the corresponding decryption keys run a threshold decryption, which is a combination of each user’s partial decryption and merging of their results. However, it has a drawback that the merging process requires communication and hence these users must be online during the process. Moreover, the computation and communication costs grow when the number of involved users increases. There is a previous work to overcome this issue by applying the idea of proxy re-encryption (PRE), where a proxy can convert a multi-key ciphertext, using re-encryption keys given by the key holders, into a ciphertext decryptable by a single receiver’s decryption key. However, a collusion of only an adversarial receiver and the single proxy can reveal the original user’s decryption key. To resolve the issue, we propose a new framework of MK-FHE with threshold PRE. Here we introduce N proxies performing re-encryption in threshold manner; now the adversarial receiver needs to collude with all of the N proxies, which becomes more difficult than the previous single-proxy case. We also propose an instantiation based on the BFV scheme and prove its security. In addition, we implement our scheme and measure the running time of its algorithms.