4
$\begingroup$

Let $H()$ be a cryptographic hash function.

Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/key?

Edit (added after 1st comment was provided): $i$ values are just integers, $r\xleftarrow{R}\mathbb{F}_p$, where $p$ is a sufficiently large prime number. Note that we want to use the above function for multiple $i$'s where $r$ is used for all but kept secret.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It depends on the encoding of i (or the exact set from which r originates) and on the exact way you model H. $\endgroup$
    – SEJPM
    Commented Jul 12, 2019 at 12:11
  • 1
    $\begingroup$ My first comment probably was a bit too vague. The problem in this construction is that there might exist $(r,i)\neq(r',i')$ with $r\|i=r'\|i'$, especially if the encoding of $i$ and the size of $r$ are of variable length. If the above is guaranteed not to happen (e.g. if $i$ is always 8 bytes) and if $H$ is a random oracle, then the construction yields a PRF and therefore derived values look random. Now of course not every hash should be modeled as a random function and it might help to know if you have any specific hash functions in mind here (e.g. Merkle-Damgard or Sponge-based ones)... $\endgroup$
    – SEJPM
    Commented Jul 12, 2019 at 17:43

1 Answer 1

Reset to default
2
$\begingroup$

Yes, only if $H(-)$ is either a $\texttt{HMAC}(-, k)$ function or an hash algorithm resistant to Length-Extension attacks1, for example, the Blake2 hash algorithm2. I'm assuming too the collision/preimage resistance, so it would be unlikely to 2 different pairs $r \ne r'$ and $i \ne i'$ collide on $H(r || i)$ = $H(r' || i')$. In this case, the $i$ index would be the key $k$ for either $\texttt{HMAC}$ or keyed-mode of the length-extension resistant hash. In fact, it is mostly how the Bitcoin HD wallets3 work to generate one-time addresses.

Due the deterministic nature of hashes, you must never reuse the same $(r, i)$ pair to generate pseudo-random values. But due this deterministic nature too, this kind of PRF is used to generate entropy where public randomness is needed, e.g, on Blockchains. On the literature, they are called Provably Fair Algorithms4,5. In such contexts, the verifiable/reproducible nature is really important to protect against cheating, the $r$ entropy would be sealed under a commitment to be revealed later for verification.

Improve this answer
$\endgroup$

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.