One embodiment provides a system that facilitates secure communication between a sending device and a receiving device. During operation, the system first transmits an encrypted message to a secure message server, wherein the encrypted message is addressed to the receiving device. The system then generates a cover message which indicates that the encrypted message is available for the receiving device. The system then transmits a digest of the cover message to a cover message server and makes the cover message available for the receiving device, thereby allowing the receiving device to confirm with the cover message server whether the cover message indicates availability of the encrypted message for the receiving device, and allowing the receiving device to obtain the encrypted message from the secure message server.