# 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

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 construction is only used in the v1.x of AEZ, because it requires appriximately 1.8 AES calls per block of plaintext, while the one used in v2.0 requires only 1 AES per block asymptotically. It is originally due to Naor and Reingold.

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).

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

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$.

The paper NR mode of operation (ps) refers to several types of functions that fit the bill if you are interested in using something else.

-