# Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?

Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size?

Say we run the key through two KDFs, and encrypt the first half of the block with the first key, and the second half of the block with the second key. This seems to give a 128-bit block cipher. However, this is probably insecure, since say if we use CTR mode both halves still become insecure by themselves.

-

One method of doing this would be to construct a Feistel network using the n-bit blockcipher as a round function. A drawback of this approach is that because you're using a blockcipher (a pseudo-random permutation) in place of a pseudo-random function, you are almost immediately limited to being secure to only $q \ll 2^{n/2}$ queries as a result of the Birthday Paradox. For $n = 64$, this could be quite problematic. (And I guess might be the type of scenario that led you to ask this question in the first place).

One way around this is to build a PRF $f_{K_1 K_2}(x) = E_{K_1}(x) \oplus E_{K_2}(x)$, where $E$ is your blockcipher. (See "The Sum of a PRPs is a secure PRF"). This is secure for $q \ll 2^{2n/3}$ queries. The result generalizes to $q \ll 2^{dn/(d+1)}$ when you XOR the outputs of $d$ independently keyed blockciphers. So you could use this for your round function. But since your round functions have to have different keys, you end up using a lot of key material, and there's a significant performance hit.

As an aside, there's a lot of literature on constructing $m$-bit "tweakable" blockciphers out of $n$-bit blockciphers for arbitrary $m > n$. This line of work is motivated mostly by full-disk encryption. See, for example, EME, HEH, HCTR. But almost all of these are again only secure up to $q \ll 2^{n/2}$ queries.

-