Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2022, Vol. 16 Issue (1) : 161809    https://doi.org/10.1007/s11704-021-0479-5
RESEARCH ARTICLE
Multi-key FHE without ciphertext-expansion in two-server model
Bingbing JIANG()
Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China
 Download: PDF(326 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Bingbing JIANG   
Just Accepted Date: 05 February 2021   Issue Date: 23 November 2021
 Cite this article:   
Bingbing JIANG. Multi-key FHE without ciphertext-expansion in two-server model[J]. Front. Comput. Sci., 2022, 16(1): 161809.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-021-0479-5
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I1/161809
1 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
9 Z P Li , C G Ma , H S Zhou . Multi-key FHE for multi-bit messages. Science China Information Science, 2018, 61 (2): 1- 3
https://doi.org/10.1007/s11432-017-9206-y
10 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
[1] Article highlights Download
[1] Lei WU, Fuyou MIAO, Keju MENG, Xu WANG. A simple construction of CRT-based ideal secret sharing scheme and its security extension based on common factor[J]. Front. Comput. Sci., 2022, 16(1): 161811-.
[2] Zhusen LIU, Zhenfu CAO, Xiaolei DONG, Xiaopeng ZHAO, Haiyong BAO, Jiachen SHEN. A verifiable privacy-preserving data collection scheme supporting multi-party computation in fog-based smart grid[J]. Front. Comput. Sci., 2022, 16(1): 161810-.
[3] Keju MENG, Fuyou MIAO, Yu NING, Wenchao HUANG, Yan XIONG, Chin-Chen CHANG. A proactive secret sharing scheme based on Chinese remainder theorem[J]. Front. Comput. Sci., 2021, 15(2): 152801-.
[4] Yudi ZHANG, Debiao HE, Mingwu ZHANG, Kim-Kwang Raymond CHOO. A provable-secure and practical two-party distributed signing protocol for SM2 signature algorithm[J]. Front. Comput. Sci., 2020, 14(3): 143803-.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed