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.
$\begingroup$
$\endgroup$
asked Sep 23, 2012 at 19:14
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
7
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, on the other hand, 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.
answered Sep 23, 2012 at 20:00
-
4$\begingroup$ 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. $\endgroup$ Feb 2, 2014 at 19:03
-
3$\begingroup$ 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. $\endgroup$ Feb 2, 2014 at 19:12
-
$\begingroup$ Would it be accurate to say that all PRPs are bijective PRFs? $\endgroup$ Feb 2, 2014 at 22:31
-
$\begingroup$ 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. $\endgroup$ Feb 2, 2014 at 22:47
-
$\begingroup$ this presentation may be helpful, and this Rogaway paper contains a neat proof of the PRP-PRF switching lemma. $\endgroup$ Mar 24, 2014 at 16:42
$\begingroup$
$\endgroup$
6
The answer is 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 are $K, X$, and $Y$. $K$ is the keyspace, $X$ the message or input space and $Y$ the output space. PRF is a function, when you give this function elements from $K$ and $X$, it will output an element from $Y$:
$$ F : K \times X \to Y $$
When you think about PRP (Pseudo Random Permutation), it also has three elements with PRP, which are $K, X, X$. As you see the input and output space are $X$:
$$ E : K \times X \to X $$
Also, a PRP is required to be bijective, and to have an efficient inversion function $\operatorname{PRP}^{-1}$. This makes sense when recalling that PRPs are sometimes called a blockcipher: The inversion function is (needed to build) the decryption function of a blockcipher.
PRFs and PRPs are both deterministic: Calling a PRF or a PRP again a same input as before will produce the same output, respectively.
The inversion function is an important difference between PRF and PRP.
Source: Slides by Dan Boneh, which also contain the common security definitions for PRFs and PRPs, and talk about the PRP/PRF Switching Lemma.
-
$\begingroup$ 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. $\endgroup$ Mar 24, 2014 at 16:49
-
2$\begingroup$ 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 $\endgroup$– tyloMar 24, 2014 at 16:57
-
$\begingroup$ 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. $\endgroup$– tyloMar 24, 2014 at 17:01
-
$\begingroup$ Thanks all. I notice my mistake and edit it. Now it should looks fine. $\endgroup$– naghceuzMar 24, 2014 at 17:41
-
$\begingroup$ 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 $\endgroup$ Mar 24, 2014 at 19:08
$\begingroup$
$\endgroup$
1
In case there's still some confusion, I'll try giving a stab at it. Anyone correct me if I'm wrong!
I believe a Pseudo Random Function tries to simulate a random function. Since a random function is just some function that has random outputs associated with inputs.
However, to make a "truly" random function is quite hard/nearly impossible. There's usually patterns/order even if you were asked to randomly pick numbers from 1-100 (for example).
Say you were able to somehow able to make a "real" random function, you'd need to store every input/output pair in memory. That's not really efficient in practice (eg. if you had to store 2^128 entries). So a PRF (Pseudo Random Function) can be expressed together like AES + the Key.
A Pseudo Random Generator is a pseudo random function with an internal state. Each time you run it, it'll run the state through a PRF, gives an output, and then updates the state using another PRF. It's pseudo random because if you re-initialize it with the same internal state, you'd end up getting the same output sequence you got previously.Unlike a PRP, a PRF does not require a one-to-one mapping between the input space and output space.
A Pseudo Random Permutation is a PRF that happens to have the property that every element in the input domain has a single associated member in the output co-domain and vice versa. This is also called a bijection (one-to-one mapping). This is why PRPs have an inverse, but PRFs don't necessarily have an inverse.
$\begingroup$
$\endgroup$
2
To me a PRP is a type of a PRF. Meaning that a PRP is where X=Y and is efficiently invertible. (NOt entirely accurate but it formed the basis of my understanding.
-
$\begingroup$ What does "efficiently invertible" mean? $\endgroup$ Jul 23, 2018 at 11:54
-
1$\begingroup$ It's not a type of PRF. In fact it's very, very different. $\endgroup$– forest ♦Jul 24, 2018 at 3:13