# How many additions modulo $2^k$ and multiplications in $\mathbb F_{2^k}$ are needed to resist cryptanalysis?

Consider a $$k$$-bit block cipher with $$r$$ rounds, and key composed of $$r$$ subkeys $$K_i\in\{0,1\}^k-\{0^k\}$$ (that is, non-zero $$k$$-bit bitstrings), for $$i\in[0,r)$$. Plaintext is $$P=S_0\in\{0,1\}^k$$, ciphertext is $$C=S_r\in\{0,1\}^k$$. At round $$i$$:

$$S_{i+1}=\begin{cases} S_i+K_i&\text{[addition in group }(\mathbb Z/2^k\mathbb Z,+)\ ]&\text{if }i\bmod 2=0\\S_i\otimes K_i&\text{[multiplication in field }(\mathbb F_{2^k},\oplus,\otimes)\ ]&\text{otherwise}\end{cases}$$

What must be $$r$$ to resist cryptanalysis? Possible declinations:

• Up to what $$r$$ are we able to exhibit an explicit polynomial-time algorithm (w.r.t. security parameter $$k$$) that distinguishes the construction from a random permutation with non-vanishing probability, given access to an encryption and decryption oracle?
• What should be $$r$$ for a given $$k$$ of practical interest (e.g. $$k\ge64$$ or larger) so that $$2^n$$ group/field operations are (conjecturally) needed to distinguishing the cipher from a random permutation, assuming say $$2^{k/2}$$ queries to an encryption and decryption oracle, and random key within the restriction that each subkey is non-zero?

We assimilate a bitstring $$B\in\{0,1\}^k$$, consisting of $$k$$ bits $$b_i$$, to integer $$B=\displaystyle\sum_{0\le j in $$[0,2^k)$$ of ring $$\mathbb Z/2^k\mathbb Z$$. We assimilate said $$B$$ to binary polynomial $$B(x)$$ of degree less than $$k$$, so that $$B(x)=\displaystyle\sum_{0\le j. Multiplication $$\otimes$$ in field $$\mathbb F_{2^k}$$ is polynomial multiplication modulo the primitive (thus irreducible) binary polynomial $$R(x)$$ of degree $$k$$ minimizing $$R(2)$$ when evaluated in $$\mathbb Z$$ (see Joerg Arndt's list, OEIS A132448).

The initial motivation was this question, which can be solved by a fast 64-bit block cipher that we can build with CLMUL now on many CPUs. That evolved to the study of a minimalist block cipher.

• While round function is minimalist, long key is not – Fractalice Jan 13 at 9:00
• @Fractalic: right. To become a practical cipher, there would be need for a key schedule. I also suspect we should avoid that the $K_i$ contain long sequences of identical bits, which leads to weaker keys. The worst weak keys are those with $K_i=1$ for all odd $i$. One idea is to force all key bytes to have odd parity, as in DES, but for a very different reason! – fgrieu Jan 13 at 9:43
• A mini question: what if $\otimes$ is changed to $\oplus$? Is there any simple attack? – Hhan Jan 16 at 2:30
• @Hhan: if we change $\otimes$ to $\oplus$, the block cipher is unsafe, because there is no propagation from hi-order bit to low-order bit (the only propagation from a bit rank to another is thru the carries, and all are towards higher-rank bit). In particular, the low-order bit of $P\oplus C$ (equivalently, $S_0\oplus S_r$) is constant, and this is enough for a distinguisher. Conjecturally, if we replaced $\otimes$ by $\oplus$ followed by any constant (non-zero) rotation, I think we'd ultimately reach security. But that (again, conjecturally) would require much more rounds. – fgrieu Jan 16 at 11:43