1
$\begingroup$

I'm reading Yao's unpredictability -> pseudorandomness construction and Goldreich/levin's pseudorandom permutation -> pseudorandom generator construction.

My question is:

is there a direct way to show that:

given a pseudorandom function, we can construct a pseudorandom permutation out of it?

[or is this question open]

Thanks!

$\endgroup$

2 Answers 2

2
$\begingroup$

That would be the celebrated Luby Rackoff result.

$\endgroup$
2
  • $\begingroup$ This answer should be expanded if it's to be useful to OP or anyyone else. $\endgroup$ Sep 29, 2011 at 19:44
  • 1
    $\begingroup$ Luby, Michael; Rackoff, Charles (April 1988), "How to Construct Pseudorandom Permutations from Pseudorandom Functions", SIAM Journal on Computing 17 (2): 373–386, dx.doi.org/10.1137/0217022 $\endgroup$
    – Kaveh
    Sep 29, 2011 at 22:52
1
$\begingroup$

To expand very slightly upon @Steve's words of wisdom, see http://en.wikipedia.org/wiki/Feistel_cipher

$\endgroup$

Your Answer

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

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