Paper 2022/273

Compact Storage for Homomorphic Encryption

Adi Akavia, Neta Oren, Boaz Sapir, and Margarita Vald

Abstract

Homomorphic encryption (HE) is a promising technology for protecting data in use, with considerable recent years progress towards attaining practical runtime performance. However the high storage overhead associated with HE remains an obstacle preventing its large scale adoption. In this work we propose a new storage solution in the two-server model resolving the high storage overhead associated with HE, while preserving data confidentiality. Our solution attains the following desired properties: 1) *Compact storage* with zero overhead over storing AES ciphertexts, and $10\times$ to $10,000\times$ better than storing CKKS ciphertexts. 2) *Fast runtime performance* for storage and retrieval, only twice the time of directly storing and retrieving HE ciphertexts. 3) *Dynamic control during retrieval* of the HE parameters and the data items to be packed in each HE ciphertext. 4) *Plug-and-play compatibility* with any homomorphic computation. We implemented our solution into a proof-of-concept system running on AWS EC2 instances with AWS S3 storage, empirically demonstrating its appealing performance. As a central tool we introduce the first perfect secret sharing scheme with fast homomorphic reconstruction over the reals; this may be of independent interest.