Structured Randomness

Imagine I want to send you a message over an insecure channel, such as the public Internet. I do not want anyone other than you to be able to learn its content. To achieve that, you and I share a secret and use it to transform the message in a way that is unpredictable to anyone who does not know the secret.

A natural idea is to pick a transformation at random and let the secret be that random choice. But describing such a choice requires far too many symbols to be practical. Instead, we build a transformation that relies on a much smaller amount of randomness, yet still looks as if it were chosen completely at random.

This thesis explores how such transformations are constructed and how their security can be assessed. It presents several analyses of the building blocks used in modern cryptographic design and takes a closer look at their underlying structure. It also introduces two new designs, each suited to different practical needs, that aim to strike the right balance between structure and randomness.