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+\log I + O(1)$ bits of information. Moreover, we give an example where this bound is tight: at least $I+\log I-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.

Fixed a minor bug. Thanks to Anup Rao and Makrand Sinha for pointing it out. Also added some open problems.

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+\log I + O(1)$ bits of information. Moreover, we give an example where this bound is tight: at least $I+\log I-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.