Hm, I think your idea of letting the search engine decrypt with your public key would solve the issue of private.sh being the untrusted party. The search engine

Hm, I think your idea of letting the search engine decrypt with your public key would solve the issue of private.sh being the untrusted party. The search engine would be able to send back the encrypted results which private.sh wouldn't be able to see. If both are untrusted parties in cahoots with each other, then there's no getting around private.sh and gigablast sharing both the IP (courtesy of private.sh) and query (courtesy of gigablast) to each other.