4
$\begingroup$

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)$

and the IND-CPA adversary game:

  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

Improve this question
$\endgroup$
4
  • $\begingroup$ CPA is chosen plaintext attack I think. What is COA? $\endgroup$
    – kodlu
    Jan 5, 2017 at 20:59
  • $\begingroup$ @kodlu ciphertext only attack $\endgroup$
    – user153882
    Jan 5, 2017 at 21:05
  • 1
    $\begingroup$ This "P-OTP", just like the regular OTP, is deterministic. $\endgroup$
    – fkraiem
    Jan 5, 2017 at 21:10
  • $\begingroup$ "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. $\endgroup$
    – Maarten Bodewes ♦
    Jan 5, 2017 at 21:15

1 Answer 1

Reset to default
4
$\begingroup$

The game you stated is not the IND-CPA game, it is the IND-EAV game, where the adversary is given only the challenge ciphertext and is asked to guess the message being encrypted. In the IND-CPA game,the adversary is given access to an encryption oracle that can encrypt arbitrary messages of his choice.

The main reason why P-OTP can not be CPA-secure is because it is deterministic, that is, if you encrypt the same plaintext twice you'll get the same ciphertext. In general, any scheme with this property can not be CPA-secure, can you figure out why?

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes ♦
    Jan 6, 2017 at 2:02
  • $\begingroup$ Then again, I'm that guy that said the state exam was incorrect (and got an addition 0.5 points for that, good sports some of those teachers). $\endgroup$
    – Maarten Bodewes ♦
    Jan 6, 2017 at 2:06
  • $\begingroup$ @MaartenBodewes I'm not sure I got you, but if you let different keys for every message then there is no point in considering CPA-(in)security for P-OTP. IMHO, the statement "P-OTP is not CPA-secure" says it all: it is not secure under chosen plaintext attacks, which involve encryptions under the same key. Am I missing something? $\endgroup$
    – Daniel
    Jan 6, 2017 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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