Cryptology ePrint Archive: Report 2022/381

On Extension of Evaluation Algorithms in Keyed-Homomorphic Encryption

Hirotomo Shinoki and Koji Nuida

Abstract: Homomorphic encryption (HE) is public key encryption that enables computation over ciphertexts without decrypting them, while it is known that HE cannot achieve IND-CCA2 security. To overcome this issue, the notion of keyed-homomorphic encryption (KH-PKE) was introduced, which has a separate homomorphic evaluation key and can achieve stronger security (Emura et al., PKC 2013).

The contributions of this paper are twofold. First, the syntax of KH-PKE supposes that homomorphic evaluation is performed for single operations, and its security notion called KH-CCA security was formulated based on this syntax. Consequently, if the homomorphic evaluation algorithm is enhanced in a way of gathering up sequential operations as a single evaluation, then it is not obvious whether or not KH-CCA security is preserved. In this paper, we show that KH-CCA security is in general not preserved under such modification, while KH-CCA security is preserved when the original scheme additionally satisfies circuit privacy.

Secondly, Catalano and Fiore (ACM CCS 2015) proposed a conversion method from linearly HE schemes into two-level HE schemes, the latter admitting addition and a single multiplication for ciphertexts. In this paper, we extend the conversion to the case of linearly KH-PKE schemes to obtain two-level KH-PKE schemes. Moreover, based on the generalized version of Catalano-Fiore conversion, we also construct a similar conversion from d-level KH-PKE schemes into 2d-level KH-PKE schemes.

Category / Keywords: public-key cryptography / Keyed-homomorphic encryption, KH-CCA security, Catalano-Fiore conversion

Date: received 23 Mar 2022

Contact author: nuida at imi kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20220328:143336 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]