A&S Departments and Programs   • Graduate Study Offered   American Studies • Anthropology • Applied Science • Art & Art History Biology • Black Studies Chemistry • Classical Studies Computer Science • Economics English Environmental Science & Policy Film Studies Geology Global Studies Government History • International Relations Kinesiology Linguistics Literary & Cultural Studies Mathematics Medieval & Renaissance Studies Military Science Modern Languages Music Neuroscience Philosophy Physics • Psychology • Public Policy • Religious Studies Sociology Theater, Speech & Dance Women's Studies

Search

Find People

Computer Science Department

Computer Science Department

Tweakable Blockciphers Secure Against Generic Exponential Attacks

Elizabeth Crump
Wednesday, April 11 3-4pm, McGl 002

Abstract

A blockcipher is a triple of algorithms, (G, E, D) where the key generation algorithm G produces a key; the encryption algorithm E takes two inputs, a key and a message, and produces a ciphertext; and the decryption algorithm D reverses the process. A blockcipher is considered secure if it is indistinguishable from a random permutation. A tweakable blockcipher is a blockcipher with an additional input, a tweak. The tweak is not meant to be kept secret, and in fact may be public knowledge, but creates variability within the cipher. A tweakable blockcipher is considered secure if it is indistinguishable from a family of random permutations indexed by the tweak.

Tweakable blockciphers were first formalized by Liskov, Rivest and Wagner, who constructed tweakable blockciphers directly from blockciphers. Crump, Goldenberg, Hohenberger, Liskov, and Seyalioglu showed that tweakable blockciphers can be constructed directly from pseudorandom functions using a Feistel model. Tweakable blockciphers have only been shown to be secure against polynomial-time adversaries, whereas the security of regular blockciphers has been proven against adversaries capable of launching generic attacks with certain specific exponential bounds. We analyze tweakable blockciphers in a comparable model, and present constructions that achieve a level of security equivalent to the best proven level of security blockciphers have attained.

Specifically, we prove that a tweak can be securely added to a seven-round Feistel construction for chosen-plaintext security, and that this construction is round optimal. We also prove that a tweak can be added to a ten-round Feistel construction for chosen-ciphertext security. In addition, we construct tweakable blockciphers that allow for longer tweak lengths; a tweak longer than the minimal size can be thought of as multiple tweaks. We prove that six rounds plus one round per tweak is sufficient for chosen-plaintext security, and eight rounds plus two rounds per tweak is sufficient for chosen-ciphertext security.