Pseudorandom Generator Behavior Assume I have an encryption scheme $E(k,m) = (P(k,r), G(r) ⊕ m) $ and given that $G$ is a PRG , $P$ is a PRP and $r$ is a random n-bit nonce.

My question is: 


  If I run this encryption twice with the same message but different r
  (due to nonce behavior), will I get the same c?


I know that PRG is deterministic, but in this case, the $r$ always changes.

Please help!
If I run this encryption twice with the same message but different $r$ (due to nonce behavior), will I get the same $c$?


No.

Lets split this question into the two elements of $c = (c_1, c_2)$ where $c_1 = P(k,r)$ and $c_2 = G(r) ⊕ m$. Then lets start with $c_2$ where the message is actually "encrypted".



A good PRF will return a stream of bits indistinguishable from random. It should be a different stream each time the seed is different. However, two random streams will still have approximately half the bits identical, purely because of chance.

So lets minimize the size of $m$ to a single bit, and set $m$ to zero. The resulting stream of bits may start with a zero or one for $r=x$ or $r=y$ with $x \neq y$ . Say that they both start with $0$ or $1$ then the result of $c_2 = G(r) ⊕ m$ will be $0$ or $1$ as well.

Of course the chance that $c_2=c_2'$ is reduced by 50% for each bit added to $m$. But $c_2$ can be identical for the right combination of nonces.



The fact that $c$ consists of the permuted nonce as well confuses the matter. The $c_1$ will always be different because $P(k, r)$ will always be different - it is a permutation after all. This has however nothing to do with the message $m$ or the security of the scheme.

However, it does mean that the only answer possible is no given your scheme; if $c_1$ is never the same then $c$ is obviously never the same as well, even though $c_2$ is not affected.



Note that $G(r)$ can only be secure if $r$ behaves as a secret, i.e. has enough entropy. The size of $r$ is maximized by the size of the PRP. Basically this scheme is a stream cipher if and only if $r$ contains enough entropy. In that case $P(k, r)$ will be a form of key wrapping.