0
$\begingroup$

Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom generators or pseudorandom functions have been constructed? That is, a function $G$ such that if any pseudorandom generators exist, then $G$ is a pseudorandom generator. Or a function $F$ such that if any pseudorandom functions exist, then $F$ is a pseudorandom function.

Now one method would be to start with Levin’s construction of a universal one-way function and then build a PRG/PRF out of that. But the construction of PRG’s and PRF’s from one-way functions is fairly complex. Is direct construction of a universal PRG or universal PRF?

$\endgroup$
2
  • 1
    $\begingroup$ So yeah, presumably the standard argument for such cases would be to construct a universal OWF from any such PRF / PRG and then use the universal OWF to construct a PRG and then a PRF. Given that in this part of cryptography concrete efficiency isn't that important I want to dampen your expectations regarding resarch in that direction. $\endgroup$
    – SEJPM
    Oct 23, 2020 at 14:21
  • $\begingroup$ @SEJPM I’m not looking for efficiency at all. I’m just looking for a universal PRG/PRF which doesn’t invoke one-way functions, because the road from one-way functions to PRG’s/PRF’s is fairly complex to state and think about. I want universal PRG/PRF which I can easily write down, or at least a procedure for constructing one which I can easily write down, even if it’s completely impractical. $\endgroup$ Oct 23, 2020 at 14:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.