I was reading Introduction to Modern Cryptography by Katz and Lindell and i found this:

Coming back to our discussion of pseudorandom functions, recall that a pseudorandom function is a keyed function F such that $F_k$ (for $k\in2 \{0, 1\}^n$ chosen uniformly at random) is indistinguishable from $f$ (for $f\in$ $Func_n$ chosen uniformly at random). The former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from all $2^{n*2n}$ functions in Funcn. Despite this, the “behavior” of these functions must look the same to any polynomial-time distinguisher.

How did he got into the conclusion that keyed function F is chosen over $2^n$ distinct functions?

Does he assume that there is a fixed function which maybe differentiated by the key k, so total of $2^n$ "functions"?


1 Answer 1


There are $2^n$ possible values for $k$, and for each one there is a function $F_k$, ergo, there are at most $2^n$ possible functions $F_k$. ("At most" is because it is possible that two different values of $k$ yield the same function $F_k$.)


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.