[phkahler]

One interesting thing about this: You are performing known operations on unknown data. But theoretically you could simulate a generic computer whose program is encrypted data as well, thus enabling unknown operations on unknown data. However, with speeds in the ms per gate we are a long way from that being practical right now.

[erikpukinskis]

> with speeds in the ms per gate

I wonder if you could write your programs in such a way that the bulk of the computation was done publically, and only sensitive ops were shunted out to the secure processing network.

Maybe in a language similar to Erlang, but instead of writing code that's amenable to sharing between multiple CPUs, you'd be sharing between multiple degrees of privacy.

[Bromskloss]

> I wonder if you could write your programs in such a way that the bulk of the computation was done publically, and only sensitive ops were shunted out to the secure processing network.

Do you have some example of what such an application may be?

[phaedrus]

Encode computations as NP hard graph optimization problems. Use the public computation resources to solve the hard part, but keep the labels of the nodes and edges in the slower encrypted computing resource.

[dllthomas]

Off the top of my head, maybe something like:

1) Secretly compute a list of encrypted tags and associated, unencrypted scores. 2) Sort by scores. 3) Convert the highest N tags back to encrypted data.

As a plus, steps 1 and 3 should be embarrassingly parallel.

You are, of course, leaking a count, which can be important (but your opponent can already make inferences based on the amount of data you have stored...).

[branja]

all the fun problems in CS are intractible

[_d4bj]

I think the OP is referring to simulating an oblivious Turing machine on the encrypted data, which itself is a Turing machine and some data.

I don't think this is known to be intractable, just really slow (for now).