Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then where is PRP used? What is PRP, where it comes to, how it benefits.
A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same domain. For instance, a cryptographically secure block cipher parametrized by a secret key is a PRP.
The term PRG is otoh most commonly used for stateful functions that are used for generating successive pseudo random strings, e.g. to be used as a key, iv, salt, nonce etc.
The answer given by Henrick is good, but I try to give a explanation with more details in security area.
When you think about PRF (Pseudo Random Function), you will think that there are three elements with PRF, which is $K, X, Y$. $K$ means the key, $X$ means the message and $Y$ means the output. PRF is a function, when you give this function $K$ and $X$, it will output a $Y$.
$$F : K \times X \to Y$$
When you think about PRP (Pseudo Random Permutation), it also have three elements with PRP , which is $K, X, X$. As you see there are two $X$. The reason it is a $X$ and not a $Y$ means that the output from PRP must be one-to-one. That is, the PRP must be a deterministic algorithm.
$$ E : K \times X \to X $$
And if you use PRP, there should be a inversion algorithm to find out the original input - $D(k,x)$
(apologize for the previous mistake, now the answer should be correct.)
If I give an input which is $m_1$ to PRF, the PRF will give me a random output, lets say it is $f_1$. Then I give $m_1$ to PRF again, this time, the PRF will give me a output but it is still $f_1$.
When I do this to PRP, I give an input $m_1$ to PRP, PRP will give me a random output which is $p_1$. Then I do this again, give PRP $m_1$, then PRP will give me $p_1$ as its output again.However, I can have a inversion function PRP^(-1)(p1) which will output m1.
The inversion function is the biggest difference between PRF and PRP
|show 1 more comment|