Paper 2022/017

Keyed-Fully Homomorphic Encryption without Indistinguishability Obfuscation

Shingo Sato
Keita Emura
Atsushi Takayasu

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

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2022
Keyed-homomorphic public key encryptionKeyed-fully homomorphic encryptionStrong DSS-NIZK
Contact author(s)
sato-shingo-zk @ ynu ac jp
k-emura @ se kanazawa-u ac jp
takayasu-a @ g ecc u-tokyo ac jp
2023-09-20: revised
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shingo Sato and Keita Emura and Atsushi Takayasu},
      title = {Keyed-Fully Homomorphic Encryption without Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/017},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.