Return to Question

Suppose having an arbitrary $GF(2^n)$ element $x$. It's 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 uniformely random and independent from each other.

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.

Suppose having an arbitrary $GF(2^n)$ element $x$. It's 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.
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 uniformely random and independent from each other.

Suppose having an arbitrary $GF(2^n)$ element $x$. It's 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 uniformely random and independent from each other.

Suppose having an arbitrary $GF(2^n)$ element $x$. It's 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.

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 uniformely random and independent from each other.

Suppose having an arbitrary $GF(2^n)$ element $x$. It's 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.
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 uniformely random and independent from each other.