Let Enc be an n-bit block cipher with n-bit secret key k. Consider the following function with 2n-bit
secret key (k1, k2):
ENC(k1,k2)(x) = Enck1 (x) ⊕ Enck2 (x).
Presumably the idea of this function (like with triple DES) is to build a new block cipher with a double sized
key (and hence to require 22n operations to break with exhaustive key search). The aim of this question is to see
if this construction is a good idea.
(a) Is it possible to efficiently decrypt this block cipher? If so, how can we do it?
(b) Suppose one is given several random pairs (xi, ci = ENC(k1,k2)(xi)), all for the same key (k1, k2). Show
that there is an attack that computes the secret key (k1, k2) in not much more than 2n+1 executions of the
function Enck, plus storing 2n binary strings of length 2n.