Hezekiah's Signet ring: no opponent May search any draw pile or discard pile.
With this wording I would say that Hezekiah's Signet ring targets you as an opponent and not your draw or discard pile.
So, I would dare to say, as long as you are personally not protected from your opponent's cards (he may throw them at you
and) his Hezekiah's Signet ring should prevent you from searching any draw pile or discard pile...
Nazareth: protect cards in your territory and hand from Shuffle by an opponent. Protect all decks from search abilities.
With the wording of Nazareth it seems that your deck would gain protection from your opponent's search abilities, but your protection protects your deck from gaining that protection