Batched Multi-hop Multi-key FHE from Ring-LWE with Compact Ciphertext Extension
Traditional fully homomorphic encryption (FHE) schemes support computation on data encrypted under a single key. In STOC 2012, López-Alt et al. introduced the notion of multi-key FHE (MKFHE), which allows homomorphic computation on ciphertexts encrypted u
- PDF / 516,023 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 143 Views
University of Chinese Academy of Sciences, Beijing, China Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing, China {chenlong,zfzhang}@tca.iscas.ac.cn 3 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China [email protected]
2
Abstract. Traditional fully homomorphic encryption (FHE) schemes support computation on data encrypted under a single key. In STOC 2012, L´ opez-Alt et al. introduced the notion of multi-key FHE (MKFHE), which allows homomorphic computation on ciphertexts encrypted under different keys. In this work, we focus on MKFHE constructions from standard assumptions and propose a new construction of ring-LWE-based multi-hop MKFHE scheme. Our work is based on Brakerski-Gentry-Vaikuntanathan (BGV) FHE scheme where, in contrast, all the previous works on multi-key FHE with standard assumptions were based on Gentry-Sahai-Waters (GSW) FHE scheme. Therefore, our construction can encrypt a ring element rather than a single bit and naturally inherits the advantages in aspects of the ciphertext/plaintext ratio and the complexity of homomorphic operations. Moveover, our MKFHE scheme supports the Chinese Remainder Theorem (CRT)-based ciphertexts packing technique, achieves poly (k, L, log n) computation overhead for k users, circuits with depth at most L and an n dimensional lattice, and gives the first batched MKFHE scheme based on standard assumptions to our knowledge. Furthermore, the ciphertext extension algorithms of previous schemes need to perform complex computation on each ciphertext, while our extension algorithm just needs to generate evaluation keys for the extended scheme. So the complexity of ciphertext extension is only dependent on the number of associated parities but not on the number of ciphertexts. Besides, our scheme also admits a threshold decryption protocol from which a generalized two-round MPC protocol can be similarly obtained as prior works.
1
Introduction
Fully homomorphic encryption (FHE) is a very attractive cryptography primitive that allows computation on encrypted data and has numerous theoretical and practical applications [Gen09,BV11b,DPSZ12,GSW13]. In STOC 2012, L´ opezAlt et al. introduced a notion of multi-key FHE (MKFHE) [LATV12], which c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 597–627, 2017. https://doi.org/10.1007/978-3-319-70503-3_20
598
L. Chen et al.
is a variant of FHE allowing computation on data encrypted under different and independent keys. One of the most appealing applications of MKFHE is to construct on-the-fly multiparty computation (MPC) protocols. L´opez-Alt et al. [LATV12] proposed the first MKFHE construction based on the NTRU cryptosystem [HPS98], which was optimized later in [DHS16]. However, the security of this construction is based on a new and somewhat non-standard assumption on polynomial rings. Clear and McGoldrick [CM15
Data Loading...
