Naor-Yung paradigm with shared randomness and applications