Paper 2015/776

Functional Encryption for Turing Machines

Prabhanjan Ananth and Amit Sahai

Abstract

In this work, we construct an adaptively secure functional encryption for Turing machines scheme, based on indistinguishability obfuscation for circuits. Our work places no restrictions on the types of Turing machines that can be associated with each secret key, in the sense that the Turing machines can accept inputs of unbounded length, and there is no limit to the description size or the space complexity of the Turing machines. Prior to our work, only special cases of this result were known, or stronger assumptions were required. More specifically, previous work (implicitly) achieved selectively secure FE for Turing machines with a-priori bounded input based on indistinguishability obfuscation (STOC 2015), or achieved FE for general Turing machines only based on knowledge-type assumptions such as public-coin differing-inputs obfuscation (TCC 2015). A consequence of our result is the first constructions of succinct adaptively secure garbling schemes (even for circuits) in the standard model. Prior succinct garbling schemes (even for circuits) were only known to be adaptively secure in the random oracle model.

Note: Corrected typos, added subsequent work.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Contact author(s)
prabhanjan va @ gmail com
History
2015-10-28: last of 3 revisions
2015-08-04: received
See all versions
Short URL
https://ia.cr/2015/776
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/776,
      author = {Prabhanjan Ananth and Amit Sahai},
      title = {Functional Encryption for Turing Machines},
      howpublished = {Cryptology ePrint Archive, Paper 2015/776},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/776}},
      url = {https://eprint.iacr.org/2015/776}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.