Multi-key FHE without ciphertext-expansion in two-server model

Abstract

López-Alt et al.(STOC12) put forward a primitive called multi-key fully homomorphic encryption (MKFHE), in which each involved party encrypts their own data using keys that are independently and randomly chosen whereby arbitrary computations can be performed on these encrypted data by a final collector. Subsequently, several superior schemes based on the standard assumption (LWE) were proposed. Most of these schemes were constructed by expanding a fresh GSW-ciphertext or BGV-ciphertext under a single key to a new sametype ciphertext of the same message under a combination of associated parties’ keys. Therefore, the new ciphertext’s size grew more or less linearly with an increase in the number of parties. In this paper, we proposed a novel and simple scheme of MKFHE based on LWE without increasing the size of the ciphertext in the two non-collusion server model. In other words, each party first independently shares their own data between two servers and each server only needs a one-round communication with another to construct a ciphertext of the same plaintext under a sum of associated parties’ keys. Our new ciphertext under multiple keys has the same size as that of the original one with only one-round communication between two servers. The communication complexity is O(kmlogq)-bit, where k is the number of input ciphertexts involved, m is the size of a GSW-ciphertext and q is a modulus. In conclusion, we proved that our scheme is CPA-secure against semi-honest adversaries.

Keywords

multi-key FHE / secret sharing / secure computation

References

[1] López-Alt A , Tromer E , Vaikuntanathan V . On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the 44th Symposium on Theory of Computing Conference. 2012, 1219- 1234

[2] Hoffstein J , Pipher J , Silverman J H . NTRU: a ring-based public key cryptosystem. In: Proceedings of the 3rd International Symposium on Algorithmic Number Theory. 1998, 267- 288

[3] Mukherjee P , Wichs D . Two round multiparty computation via multi-key FHE. In: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2016, 735- 763

[4] Clear M , McGoldrick C . Multi-identity and multi-key leveled FHE from learning with errors. In: Proceedings of the 35th Annual International Cryptology Conference. 2015, 630- 656

[5] Peikert C , Shiehian S . Multi-key FHE from lwe, revisited. In: Proceedings of the 14th International Conference on Theory of Cryptography. 2016, 217- 238

[6] Brakerski Z , Perlman R . Lattice-based fully dynamic multi-key FHE with short ciphertexts. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 190- 213

[7] Chen L , Zhang Z F , Wang X Q . Batched multi-hop multi-key FHE from ring-lwe with compact ciphertext extension. In: Proceedings of the 15th International Conference on Theory of Cryptography. 2017, 597- 627

[8] Chongcjitmate W , Ostrovsky R . Circuit-private multi-key FHE. In: Proceedings of the 20th IACR International Conference on Pratice and Theory in Public-Key Cryptography. 2017, 241- 270

[9] Li Z P , Ma C G , Zhou H S . Multi-key FHE for multi-bit messages. Science China Information Science, 2018, 61 (2): 1- 3

[10] Chen H , Chillotti I , Song Y . Multi-key homomorphic encryption from TFHE. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2019, 446- 472

[11] Zhou T P , Li N B , Yang X Y , Han Y L , Liu W C . Efficient multi-key FHE with short extended ciphertexts and less public parameters. IACR Cryptogology ePrint Archive. 2018, 2018: 1054

[12] Jiang B B , Zhang Y . Privacy-preserving min and kth min computations with fully homomorphic encryption. In: Proceedings of the 34th IEEE International Performance Computing and Communications Conference. 2015, 1- 8

[13] Jiang B B , Zhang Y . Securely min and kth min computations with fully homomorphic encryption. Science China Information Science, 2018, 61 (5): 1- 3

[14] Boyle E , Giboa N , Ishai Y . Breaking the circuit size barrier for secure computation under DDH. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 509- 539

[15] Boyle E , Giboa N , Ishai Y . Group-based secure computation: optimizing rounds, communication and computation. In: Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2017, 163- 193

[16] Boyle E , Couteau G , Giboa N , Ishai Y , Orrù M . Homomorphic secret sharing: optimizations and applications. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 2105- 2122

[17] Boyle E , Kohl L , Scholl P . Homomorphic secret sharing from lattices without FHE. In: Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2019, 3- 33

[18] Brakerski Z , Halevi S , Polychroniadou A . Four round secure computation without setup. In: Proceedings of the 15th International Conference on Theory of Cryptography. 2017, 645- 677

[19] Peikert C . Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. 2009, 333- 342

RIGHTS & PERMISSIONS

2022 Higher Education Press