Cryptology ePrint Archive: Report 2020/121

When HEAAN Meets FV: a New Somewhat Homomorphic Encryption with Reduced Memory Overhead

Hao Chen and Ilia Iliashenko and Kim Laine

Abstract: We demonstrate how to reduce the memory overhead of somewhat homomorphic encryption (SHE) while computing on numerical data. We design a hybrid SHE scheme that exploits the packing algorithm of the HEAAN scheme and the variant of the FV scheme by Bootland et al. The ciphertext size of the resulting scheme is 3-18 times smaller than in HEAAN to compute polynomial functions of depth 4 while packing a small number of data values. Furthermore, our scheme has smaller ciphertexts even with larger packing capacities (256-2048 values).

Category / Keywords: public-key cryptography / homomorphic encryption, data encoding

Original Publication (with minor differences): IMA CC 2021

Date: received 5 Feb 2020, last revised 22 Sep 2021

Contact author: ilia at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210922:095628 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]