3
$\begingroup$

In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is there a way to construct a PRF directly from an OWF?

$\endgroup$
  • $\begingroup$ I have already knew a pseudo-random-function could be constructed by this path One-Way-Function===>PRG===>PRF. I wonder is there a way like OWF===>PRF which no idea of PRG appears. $\endgroup$ – user63501 Nov 16 '18 at 1:10
  • $\begingroup$ For example, f is OWF, for key k and input x, both length n, we build $f((k+x) mod n) $ which is ${\{0,1\}}^n \times {\{0, 1\}}^n\rightarrow{\{0, 1\}}^n$. I knew above is not a PRF when k is random. But since we could assume k is random like the assumption of OWF's input is random, why we need PRG to construct a PRF rather than directly use the random assumption of k? $\endgroup$ – user63501 Nov 16 '18 at 1:28
  • $\begingroup$ @user63501 Well your construction is insecure. If you use a OWF as you say, then you need to remember that the output of a OWF can be highly biased. E.g. if $f$ is a OWF, then $f'(x):=f(x)\Vert 0$ is also a OWF, but clearly a function that always outputs $0$ as the last bit is nor a PRF. Even if you use a OWP, there are counterexamples like $f'(x\Vert b) := f(x)\Vert b$ which is a OWP iff $f$ is a OWP, but again there is a trivial attack against your construction. $\endgroup$ – Maeher Nov 16 '18 at 7:55
  • 1
    $\begingroup$ In general, I'm afraid, it's not clear what you are looking for. If you combine the constructions of GGM, HILL you get a direct construction of PRFs from OWF. So the question is why does that not satisfy you? What exactly makes a construction "direct enough" in your mind? If nobody would have told you about PRGs and just directly would have presented HILL+GGM as a construction of a PRF would you still feel that it's not direct? (This is not meant as criticism, but we need to know what you are looking for if we're going to answer the question.) $\endgroup$ – Maeher Nov 16 '18 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.