Stefano Tessaro, University of California, Santa Barbara

Abstract

Many efficient cryptographic schemes, especially in symmetric cryptography, are built from simpler building blocks such as hash functions and block ciphers, which are in turn assumed to satisfy a wide range of security properties.

Applied cryptographers have spent significant thought towards the goal of finding a simpler universal building block. In particular, a recent trend has been to base efficient symmetric cryptography on (keyless) permutations, i.e., efficiently computable and invertible one-to-one functions. From a practical standpoint, this has been very successful -- permutations have been used to build hash functions (e.g, SHA-3), authenticated encryption schemes, PRNGs, MACs, garbling schemes, and much more. From a theoretical perspective, however, the state of affairs is somewhat unsatisfactory: No good standard-model assumptions are known on such permutations, and it is unclear what kind of cryptographic hardness they provide. Security proofs for permutation-based cryptography thus inevitably end up making strong ideal assumptions on them, i.e., assuming the permutation to be random.

Our work initiates the study of security assumptions on permutations. In particular, similar to the complexity-theoretic treatment of hash functions, we enhance such permutations with a public seed, and introduce a definitional framework for the security of seeded permutations. The resulting notion, called public-seed pseudorandom permutations (or psPRP, for short), is rich in applications and an interesting object of theoretical study. This talk will give an overview, and highlight a number of open questions in the area.

Joint work with Pratik Soni.

Slides   Video