Communicating a message via a leakage-deterring encryption scheme. A sender computer stores a public key pko of a recipient key-pair (pko, sko) of a message recipient, a commitment c, bound to the public key pko, to a secret s of the message recipient, and a public key pkt of a decryptor key-pair (pkt, skt). A receiver computer stores a secret key sko of the recipient key-pair (pko, sko), the commitment c and an opening o to the commitment. A decryptor computer stores a secret key skt of the decryptor key-pair (pkt, skt). The sender computer is adapted to encrypt a message m for the message recipient by generating ciphertexts. The sender computer sends the ciphertexts to the receiver computer. The receiver computer is adapted to send a ciphertext to the decryptor computer and provide a proof. The decryptor computer is adapted to verify the proof.