Paper 2023/1443

Security with Functional Re-Encryption from CPA

Yevgeniy Dodis, New York University
Shai Halevi, AWS
Daniel Wichs, Northeastern University, NTT Research

The notion of functional re-encryption security (funcCPA) for public-key encryption schemes was recently introduced by Akavia et al. (TCC'22), in the context of homomorphic encryption. This notion lies in between CPA security and CCA security: we give the attacker a functional re-encryption oracle instead of the decryption oracle of CCA security. This oracle takes a ciphertext $c$ and a function $f$, and returns fresh encryption of the output of $f$ applied to the decryption of $c$; in symbols, $c'=Enc(f(Dec(c)))$. More generally, we even allow for a multi-input version, where the oracle takes an arbitrary number of ciphetexts $c_1,\ldots,c_\ell$ and outputs $c' = Enc(f(Dec(c_1), \ldots, Dec(c_\ell)))$. In this work we observe that funcCPA security may have applications beyond homomorphic encryption, and set out to study its properties. As our main contribution, we prove that funcCPA is ``closer to CPA than to CCA''; that is, funcCPA secure encryption can be constructed in a black-box manner from CPA-secure encryption. We stress that, prior to our work, this was not known even for basic re-encryption queries corresponding to the identity function $f$. At the core of our result is a new technique, showing how to handle adaptive functional re-encryption queries using tools previously developed in the context of non-malleable encryption, which roughly corresponds to a single non-adaptive parallel decryption query.

Available format(s)
Publication info
Published by the IACR in TCC 2023
Non-malleable encryptionCCA
Contact author(s)
dodis @ cs nyu edu
shai halevi @ gmail com
danwichs @ gmail com
2023-09-24: approved
2023-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Shai Halevi and Daniel Wichs},
      title = {Security with Functional Re-Encryption from CPA},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1443},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.