Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 2 down vote accepted

That would be the celebrated Luby Rackoff result.

share|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
1  
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 –  Kaveh Sep 29 '11 at 22:52

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

share|improve this answer

Your Answer

 
discard

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.