One embodiment of the present invention provides a system that facilitates secure messaging. The system starts by creating a message at an origin. Next, the system computes a digest of the message. This digest is signed using an origin private encryption key. The message and the signed digest are forwarded to a queue for delivery to a recipient. Upon receiving the message and the signed digest at the queue, the system verifies that the digest was signed at the origin by using an origin public encryption key. If the signature is valid, the origin cannot deny creating the message. Valid messages and digests are placed on the queue and the recipient is notified that the message is available.