Limitations of the Even-Mansour construction

In [1] a construction of a block cipher from a single pseudorandom permutation is proposed. In a complexity theoretical setting they prove that this scheme is secure against a polynomially bounded adversary. In this paper it is shown that this construction suffers from severe limitations that are immediately apparent if differential cryptanalysis [3] is performed. The fact that these limitations do not contradict the theoretical results obtained in [1] leads the authors to question the relevance of computational complexity theory in practical conventional cryptography.