Paper 2021/512

Chosen Ciphertext Secure Functional Encryption from Constrained Witness PRF

Ratna Dutta

Abstract

Functional encryption generates sophisticated keys for users so that they can learn specific functions of the encrypted message. We provide a generic construction of chosen ciphertext attacks (CCA) secure public-key functional encryption (PKFE) for all polynomial-size circuits. Our PKFE produces succinct ciphertexts that are independent of the size and depth of the circuit class under consideration. We accomplish our goal in two steps. First, we define a new cryptographic tool called constrained witness pseudorandom function (CWPRF) which is motivated by combining WPRF of Zhandry (TCC 2016) and constrained PRF of Boneh and Waters (ASIACRYPT 2013). More specifically, CWPRF computes pseudorandom values associated with NP statements and generates constrained keys for boolean functions. We can recompute the pseudorandom value corresponding to a particular statement either using a public evaluation key with a valid witness for the statement or applying a constrained key for a function that satisfies the statement. We construct CWPRF by coupling indistinguishability obfuscation (iO) and CPRF supporting all polynomial-size functions. In the second and main technical step, we show a generic construction of a CCA secure PKFE for all circuits utilizing our CWPRF. It has been observed that obtaining PKFE supporting all circuits is already a complex task and iO-based constructions of PKFEs are only proven to be chosen plaintext attacks (CPA) secure. On the other hand, existing CCA secure functional encryption schemes are designed for specific functions such as equality testing, membership testing, linear function etc. We emphasize that our construction presents the first CCA secure PKFE for all circuits along with succinct ciphertexts.

Note: We were informed of an issue in the proof of Theorem 3 concerning the use of the one-time pad u^* in hiding the challenge bit. In particular, u^* may be recoverable from functional keys, which invalidates the corresponding statistical argument. We thank Ji Luo, Ran Canetti, and Yiding Zhang for carefully pointing this out. We note that the construction may still be provably secure under a weaker notion, e.g., by restricting to a single functional key and adopting a simulation-based security model, but a full treatment must be investigated carefully.

@misc{cryptoeprint:2021/512,
      author = {Tapas Pal and Ratna Dutta},
      title = {Chosen Ciphertext Secure Functional Encryption from Constrained Witness {PRF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/512},
      year = {2021},
      url = {https://eprint.iacr.org/2021/512}
}