Secret computing: does such an animal exist?

Question

A question in theory of Computer Science

Today I can secretly store files in the cloud (say, amazon s3), by having them encrypted before I store them and decrypt them after I download. The storage provider cannot obtain any information from the stored files - everything is encrypted safely, and even symmetrical cipher will be ok here.

My question is if the same can be done with computing in the cloud. There is a computing provider in the cloud (say amazon ec2). Can I upload an "encrypted program" together with "encrypted input" for the program and have my cloud computing provider perform all the computations for me and generate for me an "encrypted output" - with the same security guarantees as in the "secret file store"?

Note that I am not talking about obfuscation and reverse engineering issues, but about secret computing with strong cryptography guarantees.

My hunch is it can't be done. Otherwise 1) it would exists, 2) my intuition is that no encrypted data can "keep being encrypted data" after transformations are applied to it, i.e. it just become gibberish.

Note Perhaps I lack the proper background in computer science, if someone could tell me what the exact nomenclature should be.

Pointers to academic literature, and clarifications regarding the concepts described above are actually called will be welcome.

Answer:

It looks that:

• secret input and output, non-secret program: Only in theory

• Secret input, secret output and secret program: not even in theory. (Update: perhaps yes, see Artelius' comment)

Answer 1

Yes, such a thing does sort of exist although it is very theoretical at the moment. It's called Homomorphic Encryption. Here's a paper about breakthroughs made at IBM and there's a comment about it on Bruce Schneier's blog.

Basically, a Homomorphic Encryption system is one where:

decrypt (f (encrypt (plaintext))) = f (plaintext)

Skizz

Answer 2

Actually, very recently someone solved the problem of what's called Fully Homomorphic Encryption. I'm not a cryptographer, but as I understand it, the basic idea is that someone could perform actions on encrypted data without even knowing what the data is, and these actions will actually have meaning (i.e., when the data is decrypted, anolagous changes will have taken place).

This has been an open problem in cryptography for a long time, and now that it's solved, technically someone could do something similar to what you propose. For example, you could upload data for Amazon's servers to work on, they could perform some kind of algorithm which is very specifically designed, and then send back your new data. (I don't know if there's a way to actually specify the algorithm itself liked you asked).

There is of course a problem with all this: it's still completely impractical, despite having been solved.

If you'd like to read more about this, I'd recommend the Wikipedia article, and also the article by Bruce Schneier "Homomorphic Encryption Breakthrough".

Answer 3

Here are some more things you may wish to read:

http://en.wikipedia.org/wiki/Secure%5Fmulti-party%5Fcomputation

http://www.cs.uiuc.edu/homes/rosulek/pubs/enc-data/enc-data.pdf

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.5151

Answer 4

Others have already pointed out the theoretic possibilities of fully homomorphic encryption, but I would like to point out that a (secret input, secret output, non-secret program)-system can be used to mke a (secret input, secret output, secret program)-system: just have the non-secret program be an interpreter for some general-purpose language and use (actual-program, input) as the input for the non-secret program.

Of course a standard computer embedded in a tamper-proof case and certified by an independent third party would be a much more practical solution.