Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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.)

Briefly speaking:

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

share|improve this answer
    
Do you have a reference for the claim that a PRF is non-deterministic? That is very different from my understanding of it: I was pretty confident that if I calculate $f(k,m)=c_1$ and $f(k,m)=c_2$ then $c_1=c_2$ - your answer suggests this is incorrect. –  figlesquidge Mar 24 at 16:49
1  
The reasoning and notation is quite off from common standards. $f:X \rightarrow X$ means, it is an endomorphism. But what you meant is an isomorphism. Just saying that the domain and range are the same structure does not imply a bijection (e.g. $\mathbb{Z} \rightarrow \mathbb{Z}: x \rightarrow 0$ is formally okay, but not a bijection). In short: A PRP is a bijective PRF. That's it. Bijective functions are invertible, but it does not mean this algorithm is efficient (or can be found easily); and this is not required from PRPs. Dont mix them with block ciphers –  tylo Mar 24 at 16:57
    
Ah, I just read the last paragraph. The non-determinism is wrong. A different output would only be possible for a different key, and this will also happen for a PRP. –  tylo Mar 24 at 17:01
    
Thanks all. I notice my mistake and edit it. Now it should looks fine. –  naghceuz Mar 24 at 17:41
    
Sorry naghceuz but your answer still isn't very clear - tylo's comment still stands about the function not necessarily being surjective (@tylo: they won't be endomorphisms/isomorphisms since you'd really hope a PRF didn't preserve significant structure on the set); "the PRF will give me a random output but it is still f1." - if its random its very unlikely to be f1 again, so you need to clarify this sentence as well –  figlesquidge Mar 24 at 19:08
show 1 more comment

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.

share|improve this answer
    
This answer is good in the sense that it provides rigorous descriptions, but I would like to know about properties that distinguish and that are shared between PRFs and PRPs. –  einnocent Feb 2 at 19:03
    
The difference between a PRF and a PRP is that the PRP is a bijective function and the PRF is not. There are no other differences, but of course this difference has various implications for their respective applications. –  Henrick Hellström Feb 2 at 19:12
    
Would it be accurate to say that all PRPs are bijective PRFs? –  einnocent Feb 2 at 22:31
    
It would be a stretch, so not quite. A PRF has to be indistinguishable from a random function. A PRP might be, but doesn't have to be, a PRF in this sense. However, the security proof for e.g. CTR mode is based on the premise that the block cipher (a PRP) might be modeled as a PRF, as long as the key stream is constrained to the square root of the cardinality of the total set of possible blocks. –  Henrick Hellström Feb 2 at 22:47
    
this presentation may be helpful, and this Rogaway paper contains a neat proof of the PRP-PRF switching lemma. –  figlesquidge Mar 24 at 16:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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