The only way to have privacy in search is not to give your queries to a 3rd party i.e. you need decentralised search.

The basic principle of decentralised search is an individual only needs a tiny fraction of all knowledge available, so the solution needs to focus on indexing their interests and social connections - see http://www.mathaware.org/mam/04/essays/smallworld.html

It has been tried already. There's YaCy https://yacy.net/en/index.html but the UX is horrible ( https://yacy.net/en/Screenshots.html ) - not for the mainstream software consumer.

Then there's http://www.faroo.com/ ( see https://en.wikipedia.org/wiki/FAROO ) which has been ticking along since 2005 and tried to appeal to consumers but arguably aliened early adopters most by targeting Windows. They seem to have stalled otherwise ( http://www.faroo.com/hp/p2p/history.html) but it still works as a service I believe.

Lastly there's https://www.bitclave.com/ - the new kid on the block. They seem to be aligning themselves with crypto-currencies somehow - perhaps there's a path there to monetisation - see https://www.cryptocoinsnews.com/bitclave-search-engine-taps-... and https://hackernoon.com/bitclave-the-decentralised-search-eng... - one to watch.