Paper 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.