Paper 2022/238

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

Abstract

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.