4
$\begingroup$

I'm currently in a course in Cryptography, and was wondering why pseudorandom function families exist at all. If there existed one pseudorandom function f(x), based on its definition, could that not be used in all cases where a pseudorandom function is needed? Why would pseudorandom functions ever need to be sampled from a family of functions?

$\endgroup$
6
$\begingroup$

By definition, a family of functions (with a given domain and codomain) is a PRF if no efficient algorithm can (with non-negligible advantage) distinguish a randomly chosen member of the function family from a function chosen at random from the entire set of functions with the same domain and codomain.

Obviously, if the family contained just one function, distinguishing it from a random function would be trivial: just feed a couple of values into the function, and check if the outputs match those from the function you're trying to distinguish from random.

For example, let's say that we have an unknown hash function $f$ with a 256-bit output, and we're trying to decide whether it is a) SHA-256, or b) a randomly chosen hash function with a 256-bit output. We can just feed the ASCII string Hello to the function, and check if the output in hexadecimal equals 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969. If it doesn't, the function definitely isn't SHA-256; if it does, it almost certainly is.

However, if we're instead trying to tell whether $f$ is HMAC-SHA-256, we can't do this unless we know the HMAC key. In this case, the set of all possible HMAC-SHA-256 functions forms a pseudorandom function family, where each function in the family is defined by a different HMAC key.

$\endgroup$
0
$\begingroup$

Yes. ​ ​ ​ A single function can only be pseudorandom in the sense of being a PRG,
but the non-key input to PRFs can be public and does not need to be uniformly distributed.

(Consider counter mode.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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