eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/810

Simulation-Based Secure Functional Encryption in the Random Oracle Model

Vincenzo Iovino and Karol Zebrowski


One of the main lines of research in functional encryption (FE) has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. -- TCC'11, O'Neill -- ePrint'10] where it was first shown that for FE the indistinguishability-based (IND) security notion is not sufficient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. -- CRYPTO'13] have shown strong impossibility results for SIM-Security. One way to overcome these impossibility results was first suggested in the work of Boneh et al. where it was shown how to construct, in the Random Oracle (RO) model, SIM-Secure FE for restricted functionalities and was asked the generalization to more complex functionalities as a challenging problem in the area. Subsequently, [De Caro et al. -- CRYPTO'13] proposed a candidate construction of SIM-Secure FE for all circuits in the RO model assuming the existence of an IND-Secure FE scheme for circuits with RO gates. This means that the functionality has to depend on the RO, thus it is not fixed in advance as in the standard definitions of FE. Moreover, to our knowledge there are no proposed candidate IND-Secure FE schemes for circuits with RO gates and they seem unlikely to exist. In this paper, we propose the first constructions of SIM-Secure FE schemes in the RO model that overcome the current impossibility results in different settings. We can do that because we resort to the two following models: In the public-key setting we assume a bound on the number of queries but this bound only affects the running-times of our encryption and decryption procedures. We stress that our FE schemes in this model are SIM-Secure and have ciphertexts and tokens of constant-size, whereas in the standard model, the current SIM-Secure FE schemes for general functionalities [De Caro et al., Gorbunov et al. -- CRYPTO'12] have ciphertexts and tokens of size growing as the number of queries. In the symmetric-key setting we assume a timestamp on both ciphertexts and tokens. This is reasonable because, in the symmetric-key setting, there is only one user that encrypts and generates tokens. In this model, we provide FE schemes with short ciphertexts and tokens that are SIM-Secure against adversaries asking an unbounded number of queries. Both results also assume the RO model, but not functionalities with RO gates and rely on extractability obfuscation w.r.t. distributional auxiliary input [Boyle et al. -- TCC'14] (and other standard primitives) secure only in the standard model.

Note: In LATINCRYPT 2015

Available format(s)
Publication info
Published elsewhere. Minor revision. In LATINCRYPT 2015
Functional EncryptionRandom Oracle ModelSimulation-Based SecurityObfuscation.
Contact author(s)
vincenzo iovino @ uni lu
2015-05-28: last of 11 revisions
2014-10-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vincenzo Iovino and Karol Zebrowski},
      title = {Simulation-Based Secure Functional Encryption in the Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2014/810},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/810}},
      url = {https://eprint.iacr.org/2014/810}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.