# Construct block cipher from a smaller one with mixing function

I read about the AEZ encryption scheme as presented at the CAESAR competition. To me it seems like a construction of an arbitrary length block cipher from a smaller one. The key component is the mixing function. (See the figure… Left: without cipher text stealing, Right: with cipher text stealing.)

Image source: http://www.cs.ucdavis.edu/~rogaway/aez/aez.pdf

In my opinion the properties of a mixing function would be:

• keyable with good avalanche effect
• no need to be cryptographically secure
• arbitrary length
• reversible
• fast (at least faster than encryption cipher)

AEZ uses reduced round AES as the core of its mixing function. Overall operation time is about 1.8 AES (as mentioned in the document). This algorithm will be bound to the AES cipher.

I wonder, is there an alternative mix function with these properties floating around?

• The pdf doesn't have the image you show, is it from a previous version (I see it's been recently updated)? – otus Aug 20 '14 at 6:39
• @otus It is on page 2 (Figure 1) – Curious Sam Aug 21 '14 at 7:01
• I just redownloaded the paper and see a completely different image on page 2. – otus Aug 21 '14 at 7:09
• @otus I can verify that with a US proxy it is now V2. Maybe the old version was cached by my ISP. The version I have is 1.1. Version 1(.0) with the same image can be found at the competition website: competitions.cr.yp.to/round1/aezv1.pdf – Curious Sam Aug 21 '14 at 8:23

It is more like a block cipher mode than a way to construct a larger block size cipher from a smaller one. Specifically, it does not improve the birthday bound which limits the number of blocks encrypted to less than the square root of block size (i.e. $2^{64}$ for AES).
The requirements for the mixing function are given in the paper above. It is enough that the functions MIX and MIXI are pairwise independent permutations, but that is not a strict requirement. Instead it is enough that they are $\epsilon$-AXU2: $\forall x \not = y, z \in \{0,1\}^n: P[f(x) \oplus f(y) = z] \le \epsilon$.