# Tag Info

2

Yes and yes, as mentioned in the comments. It is worth noting that Bitcoin wallets use a scheme similar to this in BIP32, a method of creating n various EC keypairs from a single seed deterministically: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

2

Yes, this is exactly what KDFs and PRFs are designed for. That is, no reasonably efficient attacker will be able to tell if you used an actual random key or something generated from the KDF/PRF. This is of course assuming that your initial seed/master secret was of sufficient entropy, and the way you derive the various values are not done in a silly way. ...

2

Here's a more elaborate proof for number 1. Given a distinguisher $D'$ for $F'$, we construct a distinguisher $D$ for $F$ as follows: we first pick a uniform $k_2$ of length $n$, and we run $D'$. When $D'$ asks to call its oracle on a string $x$, we give it $O_D(x) \oplus F_{k_2}(x)$ instead of $O_{D'}(x)$, where $O_D$ (resp. $O_{D'}$) is the oracle of $D$ ...

2

I think number 1 is PRF because the input key of each F is different That is correct, though I might not give full marks for your reasoning. The XOR of two PRFs is PRF. The probability that a random $k1||k2$ has $k1 = k2$ is negligible. number 2, 3, 4 are PRF because $x+k$ term could be any string of $\{0, 1\}^n$. Is that correct? This is wrong. ...

2

$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$. Let $f$ be a one-way permutation ...

1

Do NOT generate your own key derivation function. Use one of the known and trusted ones... industry standard ones, such as PBKDF2 https://en.wikipedia.org/wiki/PBKDF2 Use your starting (pseudo-random) value, and plug it into PBKDF2 for different numbers of iterations for each desired output (new seed) that you need.

1

Two suggestions: Does it simplify the problem for you if you omit n? (or only consider the n=1 case) Suppose F(x⊕1n) would not be a pseudorandom function, what does that tell you about the pseudorandomness of the original function F?

2

CTR consists of two parts: construction the key stream using a counter, and XOR-ing the output of the key stream with the plaintext/ciphertext. The key stream can be generated using a PRF, in which case it is of course not invertible. The key stream can also be created using a PRP (e.g. a block cipher like AES) in which case it is invertible. As indicated, ...

1

A $k$-wise independent hash family has the property that the joint distribution of $h(x_1), h(x_2), \ldots, h(x_k)$ is uniform when $h$ is chosen uniformly from the family (and $x_i$'s are distinct). Such families exist unconditionally (for fixed $k$), are efficient, and satisfy the condition you give. The simplest example of a 1-universal function is ...

Top 50 recent answers are included