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.

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

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

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