Cryptology ePrint Archive: Report 2022/273

Compact Storage for Homomorphic Encryption

Adi Akavia and Neta Oren and 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.

Category / Keywords: cryptographic protocols / homomorphic encryption, storage, secret sharing

Date: received 28 Feb 2022, last revised 28 Feb 2022

Contact author: adi akavia at gmail com, margarita vald at cs tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20220302:141852 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]