Paper 2019/116
Multi-Key Homomophic Encryption from TFHE
Hao Chen and Ilaria Chillotti and Yongsoo Song
Abstract
In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) which allows homomorphic evaluation of a binary gate (with bootstrapping) on ciphertexts encrypted under different keys. We generalize a low-latency homomorphic encryption scheme of Chillotti et al. (ASIACRYPT 2016) by exploiting a key-extension approach of Brakerski and Perlman (CRYPTO 2016). All the prior works on MKHE were too inefficient to be used in practice. Our construction improved the performance in terms of both asymptotic and concrete complexity: the length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. Furthermore, our scheme is fully-dynamic so that no information about the involved parties needs to be known before the computation and the resulting ciphertext can be reused in further computation with newly joined parties. To the best of our knowledge, this is the first work to implement an MKHE scheme. Our implementation takes about 0.15 (resp. 0.72) seconds to perform the gate bootstrapping when the number of involved parties is 2 (resp. 4).
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Multi-key homomorphic encryptionBootstrapping
- Contact author(s)
- Yongsoo Song @ microsoft com
- History
- 2019-09-12: last of 2 revisions
- 2019-02-07: received
- See all versions
- Short URL
- https://ia.cr/2019/116
- License
-
CC BY