I recently stumbled across "How to Run Turing Machines on Encrypted Data".

Given that it's now possible to run turing machines on encrypted data, what open problems remain in the realm of Functional Encryption?

(It seems like for every problem in Functional Encryption, one would just say: well, design a TM to compute the function, encrypt the data, then use the above scheme.)

  • $\begingroup$ My guess would be speed. It looks like asymptotically their scheme is pretty good, but by looking at how they construct their system, they probably have large constant factors in there that would kill performance in the real world. Implementation is probably non-trivial too. $\endgroup$ – mikeazo Mar 3 '14 at 16:13

Some general categories that come to mind:

  • Same functionalities from less extreme assumptions; in particular, from falsifiable ones. For example, the FE for Turing machines in GKPVZ requires SNARKs and extractable witness encryption, both of require less plausible "knowledge-type assumptions." See Gentry/Wichs
  • Or taking the above further: Succinct-ciphertext functional encryption without obfuscation. Obfuscation is likely to be slow in practice for a long time. Wouldn't it be nice if we could have, say, a practical, compact-ciphertext functional encryption scheme for P/poly from (say) the NTRU problem alone?
  • Stronger notions of security, directly. Currently, iO-based functional encryption schemes are proven selectively secure, boosted to full security by complexity leveraging, and then boosted to SIM security by De Caro et al's compiler. Being able to prove the strongest possible notions of FE security from 'first principles' would be nice.
  • Anath, et al defines a notion of delegatable functional encryption. It could be interesting to explore how far this can be taken in general.
  • Boneh, et al gives one example of a definition of function privacy for functional encryption. "Full" function privacy for all P/poly is impossible, since VBB cannot exist for all P/poly in the real world, but restricted notions may be possible for all functions (or 'full privacy' for restricted classes of functions)
  • (Disclaimer: my work) You could also consider functional encryption in a setting where the function is represented by, say, Java code: AFKLSZ
  • $\begingroup$ Note: Some very recent papers tackle parts of these problems, and others that I'm not mentioning here. $\endgroup$ – Daniel Apon Mar 7 '14 at 20:39
  • $\begingroup$ One last comment: Note that the ciphertexts in the paper you linked are asymptotically much larger than O(secparam)-bits. More recent schemes have this property (and this will essentially be a necessary property for a practical scheme); see e.g. Garg, et al for a succinct-ciphertext FE scheme $\endgroup$ – Daniel Apon Mar 7 '14 at 20:43
  • 1
    $\begingroup$ Another possibility is security against adversaries that can choose the Turing $\hspace{1.46 in}$ machines after seeing the challenge ciphertext. $\;$ $\endgroup$ – user991 Mar 7 '14 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.