June 13, Wednesday 14:15, Room 303 Jacobs Building
Title: Minimalism in Cryptography: The Even-Mansour Scheme Revisited
Lecturer: Orr Dunkelman
Lecturer homepage
: http://www.cs.haifa.ac.il/~orrd
Affiliation : University of Haifa
In this talk we consider the following fundamental problem: What is the
simplest possible construction of a block cipher which is provably secure
in some formal sense? This problem motivated Even and Mansour to develop
their scheme in 1991, but its exact security remained open for more than
20 years in the sense that the lower bound proof considered known
plaintexts, whereas the best published attack (which was based on
differential cryptanalysis) required chosen plaintexts. In this talk we
solve this open problem by describing the new Slidex attack which matches
the T = \Omega(2^n/D) lower bound on the time T for any number of known
plaintexts D. Once we obtain this tight bound, we can show that the
original two-key Even-Mansour scheme is not minimal in the sense that it
can be simplified into a single key scheme with half as many key bits
which provides exactly the same security, and which can be argued to be
the simplest conceivable provably secure block cipher. We then show that
there can be no comparable lower bound on the memory requirements of such
attacks, by developing a new memoryless attack which can be applied with
the same time complexity but only in the special case of D=2^{n/2}.
This is a joint work with Nathan Keller and Adi Shamir