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.
A López-Alt , E Tromer , V Vaikuntanathan . 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 https://doi.org/10.1145/2213977.2214086
2
J Hoffstein , J Pipher , J H Silverman . NTRU: a ring-based public key cryptosystem. In: Proceedings of the 3rd International Symposium on Algorithmic Number Theory. 1998, 267- 288
3
P Mukherjee , D Wichs . 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 https://doi.org/10.1007/978-3-662-49896-5_26
4
M Clear , C McGoldrick . Multi-identity and multi-key leveled FHE from learning with errors. In: Proceedings of the 35th Annual International Cryptology Conference. 2015, 630- 656 https://doi.org/10.1007/978-3-662-48000-7_31
5
C Peikert , S Shiehian . Multi-key FHE from lwe, revisited. In: Proceedings of the 14th International Conference on Theory of Cryptography. 2016, 217- 238
6
Z Brakerski , R Perlman . Lattice-based fully dynamic multi-key FHE with short ciphertexts. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 190- 213 https://doi.org/10.1007/978-3-662-53018-4_8
7
L Chen , Z F Zhang , X Q Wang . 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 https://doi.org/10.1007/978-3-319-70503-3_20
8
W Chongcjitmate , R Ostrovsky . Circuit-private multi-key FHE. In: Proceedings of the 20th IACR International Conference on Pratice and Theory in Public-Key Cryptography. 2017, 241- 270 https://doi.org/10.1007/978-3-662-54388-7_9
H Chen , I Chillotti , Y Song . Multi-key homomorphic encryption from TFHE. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2019, 446- 472 https://doi.org/10.1007/978-3-030-34621-8_16
11
T P Zhou , N B Li , X Y Yang , Y L Han , W C Liu . Efficient multi-key FHE with short extended ciphertexts and less public parameters. IACR Cryptogology ePrint Archive. 2018, 2018: 1054
12
B B Jiang , Y Zhang . 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
B B Jiang , Y Zhang . Securely min and kth min computations with fully homomorphic encryption. Science China Information Science, 2018, 61 (5): 1- 3
14
E Boyle , N Giboa , Y Ishai . Breaking the circuit size barrier for secure computation under DDH. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 509- 539 https://doi.org/10.1007/978-3-662-53018-4_19
15
E Boyle , N Giboa , Y Ishai . 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
E Boyle , G Couteau , N Giboa , Y Ishai , M Orrù . Homomorphic secret sharing: optimizations and applications. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 2105- 2122
17
E Boyle , L Kohl , P Scholl . 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
Z Brakerski , S Halevi , A Polychroniadou . Four round secure computation without setup. In: Proceedings of the 15th International Conference on Theory of Cryptography. 2017, 645- 677 https://doi.org/10.1007/978-3-319-70500-2_22
19
C Peikert . 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 https://doi.org/10.1145/1536414.1536461
