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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

That would be the celebrated Luby Rackoff result.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answer should be expanded if it's to be useful to OP or anyyone else. $\endgroup$
    – Marcin Kotowski
    Commented 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
    Commented 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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .