Big key encryption and the Thorp shuffle

In the bounded retrieval model, the adversary has malware on the message sender’s computer that can leak a certain amount of information (e.g., 10 percent of the size of the hard drive). In this setting, Bellare, Kane and Rogaway gave an efficient symmetric encryption scheme. Their scheme uses a giant key (a key so large that only a fraction of it can be leaked) and can be described as follows:

1. The message sender looks at the giant key at some random locations to make a key of conventional length.
2. Then she uses some standard symmetric encryption scheme, with the smaller key, to encrypt the message.
3. Then she transmits the encrypted message, along with the list of random locations where the giant key was examined.

One property of their scheme is that the encrypted message (including the list of random locations) is larger than the original message. Rogaway asked if an efficient scheme exists that does not increase the size of the message. In this talk we present such a scheme. The proof of security relies on an analysis of a card shuffle invented by Ed Thorp in 1973. No knowledge of cryptography will be assumed.

This is joint work with Hans Oberschelp and Hamilton Santhakumar.