4
$\begingroup$

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.)

Improve this question
$\endgroup$
1
  • $\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
    Commented Mar 3, 2014 at 16:13

1 Answer 1

Reset to default
9
$\begingroup$

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
Improve this answer
$\endgroup$
3
  • $\begingroup$ Note: Some very recent papers tackle parts of these problems, and others that I'm not mentioning here. $\endgroup$
    – Daniel Apon
    Commented Mar 7, 2014 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
    Commented Mar 7, 2014 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
    Commented Mar 7, 2014 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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