Crypto 2020 Best Paper Award: Chosen Ciphertext Security

By Brent Waters

At this year’s Crypto 2020 (virtual) conference, a paper that I co-authored won a Best Paper award. My co-authors were Dr. Susan Hohenberger, a research professor in the Information Security Group at the Johns Hopkins Whiting School of Engineering, and Ventaka Koppula, a member of the faculty of the Department of Computer Science and Mathematics at the Weizmann Institute of Science. We are grateful to the judges for this honor.

Here are some more details about the award and this year’s other winners, and here is the link to the recording of my presentation (see minutes 2:45 to 20:30). What follows is some background on the problem we were addressing in this paper, titled “Chosen Ciphertext Security from Injective Trapdoor Functions.”

Public key cryptography allows one party to securely encrypt information to another without having a priori secret exchange between these two users. Typically, when students first learn about public key cryptography, its security is explained in terms of “chosen plaintext security”; however, this notion only protects against “passive” attackers – attackers that simply observe a ciphertext and try to decode what the original message sent was. In real life, an attacker often has more tools at its disposal.

Suppose, for example, that a cloud storage server storing encrypted files is compromised. Also suppose that an attacker wishes to learn if the contents of an encrypted ciphertext CT is a certain message m. To do so, the attacker might perform a special modification of it to form a new ciphertext CT’ which is (still) an encryption of m if the CT was an encryption of m, but which looks invalid if it wasn’t. The cloud server then gives CT’ to the file owner’s system who attempts to decrypt it. If the file decrypts successfully, the user proceeds; otherwise, it gives a resend attack that is observed by the attacker. Thus, the attacker learns via this interaction whether the file was an encryption of m or not.

Cryptosystems that protect against such interactive or active attacks are known as chosen ciphertext secure. Chosen ciphertext security is so critical that only cryptosystems meeting these standards should be considered for deployment today.

One fundamental line of research is to learn if one can transform cryptography primitives that are only passively secure into ones that are chosen ciphertext secure. In our paper, we take a large step in this direction. We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions – a fundamental primitive that only gives passive security. This solves a longstanding problem in cryptography and provides new ideas for building chosen ciphertext secure encryption from general assumptions.