# Derive independent values using block cipher

Suppose having an arbitrary $$GF(2^n)$$ element $$x$$. Its distribution is unknown.

The task is to derive two $$GF(2^n)$$ elements $$y$$ and $$z$$, that have uniform distribution and are independent from each other.

Let $$x$$ be known to a possible adversary.

The obvious solutions are:

1. Use some KDF, but it takes a lot of time to evaluate. This operation will be used often.
2. $$y = E_k(x), z = E_k(\overline{x})$$ ($$E$$ is a block cipher), but knowing $$y$$ and $$z$$ for some $$x$$ we can easily find out $$y' = z, z' = y$$ for $$x' = \overline{x}$$.
3. $$y = E_k(x), z = E_{k'}(x)$$, but this approach uses two potentially distinct PRP's and makes more difficult the rest of one proof, so I want to avoid using distinct PRP's.
4. Let $$x$$ to be an element of $$GF(2 ^ {2n})$$ and put $$y = E_k(x[0..n]), z = E_k(x[n..2n])$$, but $$x$$ usually will be a small number, so the upper half will likely be zero.
5. Saw this question, but solutions are to use KDF's and hashes, that are too expensive in terms of performance.

I have several ideas, but I'm not sure if such $$y$$ and $$z$$ are independent.

1. Let $$y = E_k(x), z = E_k(y \oplus k')$$, where $$k'$$ is uniform, random and independent.
2. Let $$y = E_k(x), z = E_k(x \oplus k')$$, where $$k'$$ meets the same condition as for the previous option. This solution, however, has the following flaw: $$y = z \implies k' = 0$$. It potentially affects some practical security, if an adversary can intercept these values. In theory this adversary's opportunity is omitted (he or she interacts with a cryptosystem as a black-box), but if 1-st or 3-rd case produces independent values I'd prefer one of them.
3. Let $$y = E_k(x), z = y \oplus k'$$, where $$k'$$ is again uniformly random and independent.

The question is: are $$y$$ and $$z$$ independent from each other in such cases. If not, is there any "lightweight" method to derive such values.

Let $$k, k'$$ to be master-keys and $$y, z$$ to be some concrete keys I want to derive from master keys and that should differ from each other respectively for different $$x$$'s. Also they should be uniformly random and independent from each other.

If $$k$$ is uniform and independent then for fixed $$x,$$ $$\{E_k(x): k \in GF(2)^n\}$$ (assume keylength=blocklength) is in general a PRF not a PRP as $$k$$ ranges over the keyspace. Therefore it has the random balls incident in bins distribution and for two different $$k\neq k'$$ $$E_k(x)$$ may equal $$E_{k'}(x)$$ with probability approximately $$e^{-1}$$ (derangements). Therefore option 2 may have $$y$$ and $$z$$ be the same even if $$k'\neq 0.$$
You can use the PRP property directly if you treat $$x$$ as the key [fixed, with nonuniform distribution but that won't matter] for example you can define $$y=E_x(k),\quad z=E_x(k'),$$ and now these are two "one-point" samples from the same PRP that you are using and are uniformly distributed and independent.
I wonder if this or something like this would meet your requirements. If $$x$$ needs to be hidden, I suppose you could do $$x_0=H(x)$$ for some hash function and use $$E_{x_0}(\cdot)$$ instead.
• That's what I was looking for :) I forgot, that key space actually differs from message space in the second option (ah those sleepless nights spent on studying cryptography). However, the idea to use $x$ as a key looks like a better solution for my purposes Commented Jul 24, 2022 at 20:23