From what I remember from reading an ACM article on it a couple months back, you can also run the operations after they have been encrypted as well, preventing it a bit. I don't remember if there's a way to require encrypted operations, though.

In doing this, you could still brute-force operations and watch for statistically-significant results... but you'd have to guess at what valid operations are. Which amounts to the same problem as cracking the encryption in the first place, though it seems to me it would be an attack vector which weakens the encryption as a whole. To a significant degree? Don't know / doubt it.

Just don't ask me to explain the math of it. I don't know it, though I plan on studying enough to grasp it. Should take a few years.

edit: meh to the above.

Now that I've thought about it a bit longer, I do remember a decent chunk of the article dealing with information leakage, and how algorithms would need to be designed to touch as much information as possible (ideally, everything) to prevent leakage. So, it seems a map/reduce setup which combines all datapoints (removing unimportant ones further down the chain, thus hiding their influence) would be valuable.