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.


1 Answer 1


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.

  • $\begingroup$ 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 $\endgroup$ Commented Jul 24, 2022 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.