CRYPTO 11 Session 1 - Randomness and its Use

Welcome to our (almost) live coverage of CRYPTO 11.

Tom Shrimpton opened Crypto 11 announcing that all talks will be filmed an put on the web. We have a record number of attendees, well over 400.

Session 1 is on "Randomness and Its Use" chaired by Tal Rabin. I'll summarise two of the talks that I found particularly interesting - well worth viewing again online.

First talk - "Leftover Hash Lemma, Revisited"

You have some short imperfect randomness and want to derive an AES key. In theory, you can use a family of universal hash functions (with a public random seed). In the random oracle model, you can use the oracle;
in practice, you often use SHA or similar. This is not an efficiency issue (universal hash functions are very fast) but they need a much longer seed, which often makes their use impractical. Here's the new idea: take a short seed, pass it through a PRG to lengthen and then invoke a construction with the long seed. (Unfortunately this construction is not "obviously" secure.) The authors use the minicrypt model - in which there is secret key encryption but no public key encryption - to derive security for any PRG G that does not imply public-key encryption if you pick a seed s as secret key and use G(S) as the public key. (This is very likely to be the case for AES.) The construction does not work for all primitives but it does for "constructibility" ones (including signatures) and some indistinguishability ones; you can derive AES keys (for example from DH key exchange). The authors can also construct a weak PRF with their techniques which opens up many more examples. However, the one-time pad is an example of something that does not work with this construction.

Time-Lock Puzzles in the Random Oracle Model

A time-lock puzzle allows you (or, according to the speaker, your toaster) to send an encrypted puzzle to the future so that an average computer in 25 years' time can solve it easily but today's computers need 20 years to solve it. A problem is that today's attacker may use massively parallel computers (a botnet) so the puzzle should have some inherently serial characteristics. The paper uses the random oracle model and gives two results.A negative result: there is an efficient algorithm to find "intersection queries" - queries asked both by the puzzle setter and solver - ruling out many types of constructions. A positive result: the authors give a chaining construction (repeatedly asking the oracle at inputs depending on its previous output). (The authors do not solve the problem of your toaster burning the toast while it is working on time-lock puzzles.)