5
$\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$
8
$\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.

| improve this answer | |
$\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.)

| improve this answer | |
$\endgroup$
0
$\begingroup$

You could have a single pseudo-random function that is secret to you. To anyone else its computation at some value will look random. The reason we choose to have a public family of functions and a secret key is inspired by a principle known as Kerckhoff's Principle. Kerckhoff recognized that a compromised private encryption scheme (i.e your single private function) is worse than a compromised private key of a public scheme (i.e your HMAC key). I think the relevant section to read is: "Explanation of the Principle" one in this wikipedia article: https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle

| improve this answer | |
$\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.