I have understood the "equivalences" between PRP, PRF and PRG. Now, I just read an statement in my lecture notes that made me think that there has to be a conversion between PRG and computationally secret encryption scheme:

So, our definition of PRG is sufficient for the existence of a computationally secret encryption scheme. Later, we will see that this is definition is the right one as PRGs exist if computationally secret encryption schemes exist.

This means I can build a PRG from a computationally secret encryption scheme. What is the common and easy way to see this?

  • $\begingroup$ ... create a key stream using a stream cipher or in streaming mode? $\endgroup$ – Maarten Bodewes Dec 3 '18 at 0:01

I don't know of any direct way of doing this. In particular, in contrast to the way most encryption schemes work in practice, in theory there is no requirement that the output of an encryption scheme look random at all. The only way that I know to do this is to prove that computationally secret encryption implies one-way functions (not hard to show, but not completely trivial, since it is only true when the amount being encrypted is larger than the key size). Then, using HILL, one can construct a PRG from any one-way function.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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