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

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