We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing I bits of information, the transmission can be simulated without private coins using I+logI+O(1) bits of information. Moreover, we give an example where this bound is tight: at least I+logI−O(1) bits are necessary in some cases. Our example also shows that the one-round compression construction of Harsha et al. [HJMR07] cannot be improved.