Paper 2022/238

HEAD: an FHE-based Privacy-preserving Cloud Computing Protocol with Compact Storage and Efficient Computation

Lijing Zhou, Huawei Technology
Ziyu Wang, Huawei Technology
Hongrui Cui, Shanghai Jiao Tong University
Xiao Zhang, Huawei Technology
Xianggui Wang, Huawei Technology
Yu Yu, Shanghai Jiao Tong University

Fully homomorphic encryption (FHE) provides a natural solution for privacy-preserving cloud computing, but a straightforward FHE protocol may suffer from high computational overhead and a large ciphertext expansion rate, especially for computation-intensive tasks over large data, which are the main obstacles toward practical privacy-preserving cloud computing. In this paper, we present HEAD, a generic privacy-preserving cloud computing protocol that can be based on most mainstream (typically a BGV or GSW style scheme) FHE schemes with more compact storage and less computational costs than the straightforward FHE counterpart. In particular, our protocol enjoys a ciphertext/plaintext expansion rate of 1 (i.e., no expansion) in a cloud computing server, instead of a factor of hundreds of thousands. This is achieved by means of ``pseudorandomly masked'' ciphertexts, and the efficient transformations of them into FHE ciphertexts to facilitate privacy-preserving cloud computing. Depending on the underlying FHE in use, our HEAD protocol can be instantiated with the three masking techniques, namely modulo-subtraction-masking, modulo-division-masking, and XOR-masking, to support the decimal integer, real, or binary messages. Thanks to these masking techniques, various homomorphic computation tasks are made more efficient and less prone to noise accumulation. Furthermore, our multi-input masking and unmasking operations are more flexible than the FHE SIMD-batching, by supporting an on-demand configuration of FHE during each cloud computing request. We evaluate the performance of HEAD protocols on BFV, BGV, CKKS, and FHEW schemes based on the PALISADE and SEAL libraries, which confirms the theoretical analysis of the storage savings, the reduction in terms of computational complexity and noise accumulation. For example, in the BFV computation optimization, the sum or product of eight ciphertexts overhead is reduced from 336.3 ms to 6.3 ms, or from 1219.4 ms to 9.5 ms, respectively. We also embed HEAD into a mainstream database, PostgreSQL, in a client-server cloud storage and computing style. Compared with a straightforward FHE protocol, our experiments show that HEAD does not incur ciphertext expansion, and exhibits at least an order of magnitude saving in computing time at the server side for various tasks (on a hundred ciphertexts), by paying a reasonable price in client pre-processing time and communication. Our storage advantage not only gets around the database storage limitation but also reduces the I/O overhead.

Available format(s)
Cryptographic protocols
Publication info
Fully homomorphic encryption
Contact author(s)
zhoulijing @ huawei com
wangziyu13 @ huawei com
rickfreeman @ sjtu edu cn
zhangxiao81 @ huawei com
wangxianggui1 @ huawei com
yuyu @ cs sjtu edu cn
2022-08-20: last of 3 revisions
2022-02-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lijing Zhou and Ziyu Wang and Hongrui Cui and Xiao Zhang and Xianggui Wang and Yu Yu},
      title = {HEAD: an FHE-based Privacy-preserving Cloud Computing Protocol with Compact Storage and Efficient Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/238},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.