Paper 2014/588

A Punctured Programming Approach to Adaptively Secure Functional Encryption

Brent Waters


We propose the first construction for achieving adaptively secure functional encryption (FE) for poly-sized circuits (without complexity leveraging) from indistinguishability obfuscation (iO). Our reduction has polynomial loss to the underlying primitives. We develop a "punctured programming'' approach to constructing and proving systems where outside of obfuscation we rely only on primitives realizable from pseudo random generators. Our work consists of two constructions. Our first FE construction is provably secure against any attacker that is limited to making all of its private key queries after it sees the challenge ciphertext. (This notion implies selective security.) Our construction makes use of an we introduce called puncturable deterministic encryption (PDE) which may be of independent. With this primitive in place we show a simpleconstruction FE construction. We then provide a second construction that achieves adaptive security from indistinguishability obfuscation. Our central idea is to achieve an adaptively secure functional encryption by bootstrapping from a one-bounded FE scheme that is adaptively secure. By using bootstrapping we can use "selective-ish'' techniques at the outer level obfuscation level and push down the challenge of dealing with adaptive security is then FE scheme, where it has been already been solved. We combine our bootstrapping framework with a new "key signaling'' technique to achieve our construction and proof.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Functional EncryptionObfuscation
Contact author(s)
bwaters @ cs utexas edu
2015-01-09: revised
2014-07-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Brent Waters},
      title = {A Punctured Programming Approach to Adaptively Secure  Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/588},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.