1

For a while the concept of Homomorphic encryption has existed which is the concept of encrypting data and still being able to manipulate it as if it was unencrypted.

Would it be theoretically possible to create a scheme such that not only the data is encrypted and hidden but the functions to manipulate the data can also be encrypted into new functions so that way not only can the computations be done off site without revealing the original data but the very functions/form of the data also remains hidden?

The use of a such a "second order" Homomorphic encryption scheme would be enormous for obvious reasons. The one hurdle appears to be transforming any type of data manipulation into a different form that can always be mapped back.

Seeing that standard Homomorphic encryption has been achieved (albeit impractical) through Craig Gentry's work I see some hope for this 2nd order scheme.

Sidharth Ghoshal
  • 16,771

1 Answers1

0

Of course it is theoretically possible, at the cost of a lot of efficiency, by introducing another layer of interpretation.

If you have a system that lets a service provider run an arbitrary known program on encrypted data, you can let the known program be a universal program, and then the encrypted data is the encryption of a pair of a user program (now unknown to the service provider) and the actual data it works on.

Whether a scheme of this sort can be made with sufficiently small overhead costs to be practical is of course a different matter.

(In the schemes I have seen presentations of, it would be more appropriate to say "circuit" instead of "program", but hardware and software are equivalent from a sufficiently abstract point of view).

hmakholm left over Monica
  • 286,031
  • Given the recent work on Homomorphic encryption they got it down to an O(n^(3.5)) expansion on the data of size n. how much more can that be cut? – Sidharth Ghoshal Oct 10 '13 at 18:48
  • 1
    @Henning, More formally that would be achieving "operational privacy" through "Generalization" rather than "obfuscation". More details are coming in my work in progress paper on the same. Also the universal program you mean universal boolean circuits ? or you have some thing else in mind? – sashank Oct 15 '13 at 02:19
  • universal boolean circuits – Sidharth Ghoshal Oct 15 '13 at 17:52