Public Key Encryption Against Related Key Attacks

In the first of his three talks at this year's PKC in Darmstadt, Hoeteck Wee (George Washington University) discussed his paper on linear related key attacks (RKAs) [pdf]. The paper presents public key schemes that are resilient against RKAs under standard assumptions in the standard model, in which the ciphertext overhead is only an additive constant number of group elements.

The security definition is that of Bellare et al. [pdf] with attacks on the secret key of the public key schemes, so the focal point is chosen-ciphertext related key attacks (CC-RKA). In this setting an adversary sends decryption queries of the form (C , Δ) where Δ is the linear shift, and the oracle responds with a decryption of ciphertext C under sk + Δ. It is important to note that linear shifts do not capture practical attacks, but this is an important step in understanding RKAs as a whole.

In this attack the decryption oracle refuses to act only when the ciphertext it is given matches the challenge ciphertext and the derived key equals the real one. One can modify this attack model to what is called 'weak-CC-RKA' where the decryption oracle refuses to act whenever the ciphertext it is given matches the challenge ciphertext.

The paper presents strong public key encryption based on bilinear DDH and the hardness of factoring, and weak-CC-RKA schemes based on DDH and LWE. The constructions exploit two properties: 'key homomorphism', which means that the decryption of a ciphertext C using a secret key (sk + Δ) equals the decryption of some other (efficiently computable) ciphertext C' using the original secret key sk, and 'fingerprinting' meaning it is hard to maul cipertexts in a meaningful way, to avoid querying Dec(sk , ·) on the challenge ciphertext (more details in the paper).

The constructions based on bilinear DDH and standard DDH require strong one-time signature schemes based on discrete log. The LWE based scheme utilises trapdoors for lattices, as devised by Micciancio and Peikert [pdf] - the trapdoor for inverting f_A(s) = As + e is key homomorphic. The technique of Hofheinz and Kiltz [pdf] to base security on the hardness of factoring is employed along with one-time signatures to fulfill the two properties described above and create a strong IND-CC-RKA scheme.

Naturally the main open problem is developing schemes that are secure against a larger class of attacks, while keeping the overhead as low as possible.