MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]


share|cite|improve this question
up vote 2 down vote accepted

That would be the celebrated Luby Rackoff result.

share|cite|improve this answer
This answer should be expanded if it's to be useful to OP or anyyone else. – Marcin Kotowski Sep 29 '11 at 19:44
Luby, Michael; Rackoff, Charles (April 1988), "How to Construct Pseudorandom Permutations from Pseudorandom Functions", SIAM Journal on Computing 17 (2): 373–386, – Kaveh Sep 29 '11 at 22:52

To expand very slightly upon @Steve's words of wisdom, see

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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