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