Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Such "second order" thing is called "operational privacy" in the literature. – sashank Oct 15 '13 at 2:16
up vote 0 down vote accepted

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

share|cite|improve this answer
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? – frogeyedpeas Oct 10 '13 at 18:48
@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 2:19
universal boolean circuits – frogeyedpeas Oct 15 '13 at 17:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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