Cryptology ePrint Archive: Report 2020/1335

Hybrid Framework for Approximate Computation over Encrypted Data

Jihoon Cho and Jincheol Ha and Seongkwang Kim and Joohee Lee and Jooyoung Lee and Dukjae Moon and Hyojin Yoon

Abstract: Homomorphic encryption (HE) is a promising cryptographic primitive that enables computation over encrypted data, with various applications to medical, genomic, and financial tasks. In such applications, data typically contain some errors from their true values. The CKKS encryption scheme proposed by Cheon et al. (Asiacrypt 2017) supports approximate computation over encrypted data. However, HE schemes including CKKS commonly suffer from slow encryption speed and large ciphertext expansion compared to symmetric cryptography.

To address these problems, in particular, focusing on the client-side online computational overload and the ciphertext expansion, we propose a novel hybrid framework that supports CKKS. Since it seems to be infeasible to design a stream cipher operating on real numbers, we combine the CKKS and the FV homomorphic encryption schemes, and use a stream cipher using modular arithmetic in between. The proposed framework is thus dubbed the CKKS-FV transciphering framework. As a result, real numbers can be encrypted without significant ciphertext expansion or computational overload on the client side.

As a stream cipher to instantiate the CKKS-FV framework, we propose a new HE-friendly cipher, dubbed HERA, and analyze its security and efficiency. HERA is a stream cipher that features a simple randomized key schedule (RKS). Compared to recent HE-friendly ciphers such as FLIP and Rasta using randomized linear layers, HERA needs smaller number of random bits, leading to efficiency improvement on both the client and the server sides.

Our implementation shows that the CKKS-FV framework using HERA is $3.634$ to $398$ times faster on the client-side, compared to the environment where CKKS is only used, in terms of encryption time. Our framework also enjoys $2.4$ to $436.7$ times smaller ciphertext expansion according to the plaintext length.

Category / Keywords: secret-key cryptography / homomorphic encryption, transciphering framework, stream cipher, HE-friendly cipher

Date: received 23 Oct 2020, last revised 26 Oct 2020

Contact author: ksg0923 at kaist ac kr,smilecjf@kaist ac kr,hicalf@kaist ac kr

Available format(s): PDF | BibTeX Citation

Version: 20201027:054759 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]