Paper 2022/017

Keyed-Fully Homomorphic Encryption without Indistinguishability Obfuscation

Abstract

(Fully) homomorphic encryption ((F)HE) allows users to publicly evaluate circuits on encrypted data. Although publicly homomorphic evaluation property has various applications, (F)HE cannot achieve security against chosen ciphertext attacks (CCA2) due to its nature. To achieve both the CCA2 security and homomorphic evaluation property, Emura et al. (PKC 2013) introduced keyed-homomorphic public key encryption (KH-PKE) and formalized its security denoted by $\mathsf{KH\textup{-}CCA}$ security. KH-PKE has a homomorphic evaluation key that enables users to perform homomorphic operations. Intuitively, KH-PKE achieves the CCA2 security unless adversaries have a homomorphic evaluation key. Although Lai et al. (PKC 2016) proposed the first keyed-fully homomorphic encryption (keyed-FHE) scheme, its security relies on the indistinguishability obfuscation ($\mathsf{iO}$), and this scheme satisfies only a weak variant of $\mathsf{KH\textup{-}CCA}$ security. Here, we propose a generic construction of a $\mathsf{KH\textup{-}CCA}$ secure keyed-FHE scheme from an FHE scheme secure against non-adaptive chosen ciphertext attack (CCA1) and a strong dual-system simulation-sound non-interactive zero-knowledge (strong DSS-NIZK) argument system by using the Naor-Yung paradigm. We show that there are existing strong DSS-NIZK systems and IND-CCA1 secure FHE schemes that are suitable for our generic construction. This shows that there exists a keyed-FHE scheme from simpler primitives than iO.