Difference between secure PRG and and semantically secure

1.2k views Asked by At

I am taking cryptography course in coursera by Stanford University. and I have following question.

I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is considered as not secure PRG as 0 in message is copied with out encryption. Whereas in semantically secure E'(k,m) = 0 || E(k,m) i.e., prepend 0 is considered as semantically secure. Here why appending 0 does not break semantically secure?

Kindly request to clarify.

1

There are 1 answers

0
Marek Klein On

You are comparing two different things. One is a PRG (pseudo random generator) and the other one is, I believe, PRP (pseudo random permutation).

PRG has only one input, the key, and the output should be random enough to be indistinguishable from true random block. It means that when adversary looks at the string he is not able to decide whether the output is from PRG or whether it is a truly random block. However, when you append 0 you can easily distinguish whether you use true random generator or G' (because true random ends with 0 only in a half of all the cases while G' always ends with 0).

In the second case an adversary wants to find some information about plaintext m. We assume E(k,m) is secure. Now the question is: is E'(k,m) secure? Does the prepended 0 give you some information on the plaintext m? If so, it means that you have "a tool" that extracts some information about m from E'(k,m). If you have such tool, can you use it to break E(k,m)? Yes you can. You can get output of E(k,m), prepend a 0 and pass it to your tool. Voila you just broke E(k,m) but it means that our assumption that E(k,m) is secure is incorrect.