1
$\begingroup$

In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then there are $(2^{128})^{(2^{128})}$ different functions that map the set $X$ to the set $Y$.

I guess that's because we can see this as a sampling with replacement : for each element in $X$ we pick a random element in $Y$, and replace the element in $Y$ before picking again. Once we're done, that make a random mapping from $X$ to $Y$, and so there are $(2^{128})^{(2^{128})}$ possible mappings.

What about PRPs? Because in a PRP the mapping functions must be invertible, can we see them as a sampling without replacement? And so, the number of possible functions from $X$ to $Y$ for a PRP should be $(2^{128})!$, is that right?

$\endgroup$
  • 2
    $\begingroup$ Welcome to crypto.se! Your question is a tad basic, but yes, are just right (if you add that $X$ and $Y$ must be of same size in the case of a PRP). Notice that we can use MathJax. $(2^{128})^{(2^{128})}$ is written $(2^{128})^{(2^{128})}$. More here. $\endgroup$ – fgrieu Oct 22 '16 at 9:34
  • $\begingroup$ @fgrieu I'm just trying to get a better understanding of what PRFs and PRPs are. It probably looks obvious to you, it's not so much the first time you meet these concepts. Thanks for the pointer to MathJax though. $\endgroup$ – anselant Oct 22 '16 at 21:07
2
$\begingroup$

Yes, that's right. This is also why the key size can be much larger than the block size. The idea of a (well-distributed) key is that it pseudo-randomly chooses a function from X to Y.

So for instance AES can have a block size of 128 and a key size of 256 (and it has) because there are "only" $2^{256}$ keys while there are $2^{128}!$ possible functions / permutations. This is more explicitly explained here.

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