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.

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