# Randomness of recursive sequence generation

How good from a randomness point of view are recursively generated sequences using good encryption algorithms?

Let us say I take AES128 which generates good random sequences of outputs for counter inputs. Denote C=E(K,P) to be the output of AES128 with symmetric key K and input block P. Consider the recursively generated sequence

Q(i)=E(K,Q(i-1)) for i=1,2,3,...

• where Q(0) is a random 128-bit block chosen as the initial seed.
• Assume that K is also chosen randomly.

Is there a theoretical basis to presume that the sequences Q(i) will also satisfy good randomness properties?

• Thank you Rohit Gupta for editing the question. What is the model of randomness you are suggesting for the recursive sequence? I am interested in the complexity of the sequence as an attribute of randomness. Jan 17 at 5:10

TL;DR

Under standard assumptions on block cipher design (which in the case of AES have been also experimentally tested and no bad surprises have been found) the function $$Q$$ generating a recursive sequence is a pseudorandom function with the expected properties of such a function, e.g., the average and maximum cycle length.

Edit:

The maps below derived from $$E_K(P):=E(K,P)$$ can be assumed to have pseudorandom properties for the cases $$f:K\mapsto C:\quad f(K):=E(K,P),\quad \forall \textrm{ fixed } P,\\ g:P\mapsto C:\quad g(P):=E(K,P),\quad \forall \textrm{ fixed } K.\\$$ If in addition the blocklength is equal to the keylength then they can be assumed to be pseudorandom permutations on the same space $$\{0,1\}^n.$$ This leads to the conclusion in the comments that the sequences $$C(i)=f(C(i-1))$$ starting from $$C(0)=f(K_0)$$ when $$C(0)$$ is given but $$K_0$$ is inaccesible should also satisfy randomness tests.

However, this sequence now behaves like a pseudorandom function as opposed to a pseudorandom permutation, traversing the space $$\{0,1\}^n.$$ Flajolet and Odlyzko, in "Random Mapping Statistics", EUROCRYPT ’89, 329–354 have analyzed the statistics of such maps, in terms of the lengths of the cycles they form, etc. specifically for DES. However, there is theoretical work in this domain from Kolchin as well as from Graham. I think we can consider the (logarithm of) the expected cycle length as one measure of the randomness. Otherwise we can consider the maximum cycle length as a measure of maximum possible randomness.

If we apply Flajolet and Odlyzko's results to AES, we obtain that the expected cycle length of the mapping is $$O(\sqrt{2^{128}})$$ and and the maximum cycle length of the mapping is of the same order.

However, in real life, we do not have "chosen key" attacks but we do have "chosen plaintext" attacks. The key is the target of the attack. So in terms of modeling real attacks, the roles of the two maps $$f,g$$ above are not identical. And as I already stated, structural properties of the specific cipher design may also mean that the way $$K$$ and $$P$$ are processed through the rounds of the cipher is not the same.

You already assume $$E_K(P)\mapsto C$$ has good randomness properties: Let us say it is hard to distinguish from a random permutation for any fixed $$K$$ or fixed $$P$$ if seen as a multivariate input function with $$K$$ as an input.
Assuming this, and that the initial state $$Q(0)$$ is random the sequence $$Q(i),i\geq 1$$ is then also random, and will typically not be distinguishable from random until you iterate it more than $$k\geq \sqrt{2^{128}}$$ times.
• yes I informally iplied that in my answer as well, however, in block cipher designs the roles of $K$ and $P$ may not be interchangeable, so this would need further proof/verification in general. Jul 19, 2022 at 1:36