Speaker: Stefano Tessaro, UC Santa Barbara
Title: Provably secure block ciphers from keyless functions: Full-domain and related-key security
Abstract.
We consider the problem of building a keyed family of permutations
(i.e., a block cipher) from a (keyless) function. The resulting block
cipher is meant to be a secure pseudorandom permutation (PRP) in a
model where the underlying function is randomly chosen and public,
i.e., it can be evaluated by the adversary. This model was initially
introduced by Even and Mansour for the case where the underlying
function is a permutation.
In this talk, I present the first construction achieving nearly
optimal security in this model, i.e., the construction is a secure PRP
even when the attacker can query nearly all of the domain of the
cipher and of the underlying function. I will also show a variant of
the construction that remains secure under a large class of
related-key attacks. Unlike most previous works, these constructions
do not assume that the underlying function is invertible (i.e., it is
itself a permutation).
On the way, I will also discuss the importance of the theory behind
such constructions, and highlight interesting theoretical challenges
in this area.