We use PRG to encrypt the message $$m$$ in the case of Pseudo one time pad instead of random string as in one time pad. Assuming G is PRG we prove that the scheme Pseudo one time pad is computationally indistinguishable with probability $$\frac{1}{2}+$$ negligible.

What will be success probability of the adversary for Pseudo one time pad when computationally unbounded adversary is considered? I am considering here the challenge adversary game where $$m_0$$ or $$m_1$$ is encrypted and sent to adversary.

The success probability of a computationally unbounded adversary against a pseudo one time pad is almost close to $$1$$. Let us take a concrete example. Consider a secure pseudorandom generator $$G : \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2 \lambda}$$ and let the message size by $$2 \lambda$$. The unbounded adversary chooses two messages $$m_0, m_1 \in \{0,1\}^{2\lambda}$$ independently and uniformly at random and receives a ciphertext $$ct = m_b \oplus G(s)$$ where $$s \in \{0,1\}^{\lambda}$$ is a randomly chosen secret key by the challenger.

We need to bound the probability that $$ct$$ is also an encryption of $$m_{1-b}$$. That is, the probability $$m_{1-b} \in \{ct \oplus G(t) \;|\: \forall t \in \{0,1\}^{\lambda}\}$$. Observe that since $$m_{1-b}$$ is chosen independent of $$m_b$$ and uniformly at random, the probability is at most $$\frac{2^{\lambda}}{2^{2\lambda}} = \frac{1}{2^{\lambda}}$$ by union bound. In other words, with negligible probability there will exist a $$t \in \{0,1\}^{\lambda}$$ such that $$ct = m_{1-b} \oplus G(t)$$ (i.e., $$ct$$ is a valid encryption of both $$m_0$$ and $$m_1$$).

The unbounded adversary would go over all the values of $$t \in \{0,1\}^{\lambda}$$ and check if $$ct = m_0 \oplus G(t)$$ or $$ct = m_1 \oplus G(t)$$ and return the correct value with high probability.

One does not need to speak of negligible probability, the adversary can win with probability 1.

Assume the binary case (other cases are similar). Note that the adversary is able to choose both $$m_0$$ and $$m_1$$ without constraint. Given a choice of $$2^\lambda$$ possible seeds they construct all generated pseudo-pads of length $$2^{2\lambda-1}$$ and all possible $$\Delta$$s of these key streams. Now note that there are $$\binom{2^\lambda}2$$ possible $$\Delta$$ streams which is less than the number of possible non-pseudo-pads. The adversary chooses a $$\Delta$$ stream $$\Delta_a$$ that does not occur in the list of pseudo-$$\Delta$$ streams, chooses an arbitrary $$m_0$$ and sets $$m_1:=m_0+\Delta_a$$. Whichever choice of irrespective of whether $$m_0$$ or $$m_1$$ is selected for encryption, the other message is not a possible decryption under any choice of key.

• Does this still hold if the PRG is computationally unbound? Commented Aug 7 at 21:45
• @PaulUszak I think so, yes; it relies only on the PRG being deterministic -- i.e. given its seed, the adversary knows what it will do. Commented Aug 7 at 22:22

A computationally unbounded adversary could consider all possible PRG seeds, and try them all to see if the ciphertext decrypts to either $$m_0$$ or $$m_1$$. Unless there is an incorrect seed that decrypts the ciphertext to the wrong message (we know that there is one that decrypts the ciphertext to the correct message), the adversary will be able to tell which one is the correct one.

And, as long as $$m_0, m_1$$ is considerably longer than the seed, the probability that there will be an incorrect seed is negligible.