# Why is pseudorandom OTP (P-OTP) IND-CPA insecure

My lecture notes state that P-OTP is IND-COA but not IND-CPA insecure. I understand IND-COA secure, assuming PRG is secure, as that is the whole point of a OTP, but why is it IND-CPA insecure? Surely, if the PRG is assumed to be secure, then the resulting ciphertext would be random, so whatever plaintext you feed into the oracle will reveal no information.

I ask this because PRF+OTP is IND-CPA secure and cannot figure out the difference.

$Enc_k(m)=m\oplus PRG(k)$

$Dec_k(c)=c\oplus PRG(k)$

1. Pick two messages $m_0$ and $m_1$ arbitrarily.
2. Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c_1=Enc_k(m_1)$.
3. Output your guess for $b$ named $b'$. You "win" iff $b=b'$.

Edit: screenshots of the relevant slides

• CPA is chosen plaintext attack I think. What is COA? – kodlu Jan 5 '17 at 20:59
• @kodlu ciphertext only attack – user153882 Jan 5 '17 at 21:05
• This "P-OTP", just like the regular OTP, is deterministic. – fkraiem Jan 5 '17 at 21:10
• "In a chosen-plaintext attack the adversary can adaptively ask for the ciphertexts of arbitrary plaintext messages. This is formalized by allowing the adversary to interact with an encryption oracle, viewed as a black box. The attacker’s goal is to reveal all or part of the secret encryption key." - well, if you consider the key to be the output of the PRNG then you've got an attack, but that would go for regular OTP or stream ciphers as well. You can also proof that a seed is not used, but again, same thing with the other schemes. I don't see it either. – Maarten Bodewes Jan 5 '17 at 21:15

On the other hand, PRF+OTP is not deterministic: it refreshes each encryption with a random value $r$. This key difference makes the scheme CPA-secure, the proof can be found in any basic book like Katz' Modern Cryptography (Thm 3.31 in the 2nd edition), but the basic idea is that if the value $r$ is not repeated in the oracle's queries, then the attacker get no information about the message being encrypted (so you have perfect secrecy in this case, just like in the OTP), and the probability that this does not occurre is small enough.
• You're probably correct, but I think it is kinda unfair. In the slides OTP is $E_k(m) = k \oplus m$ while P-OTP is $E_k(m) = \operatorname{PRG}(k) \oplus m$. Now from that you'd expect a new message to be encrypted with a different $k$ for both OTP and P-OTP otherwise OTP would have the same issue as P-OTP. So if this is the issue, it is not communicated all that well (in my opinion anyway). – Maarten Bodewes Jan 6 '17 at 2:02