Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure.

1. To encrypt $m \in \{0, 1\}^{n+1}$ choose a random $r \leftarrow \{0, 1\}^n$ and output $[r, G(r) \oplus m]$

2. To encrypt $m \in \{0, 1\}^{n}$ output $m \oplus F_k(0^n)$

3. To encrypt $m \in \{0, 1\}^{2n}$ choose a random $r \leftarrow \{0, 1\}^n$ and send $[r, m \oplus (F_k(r) \; | \; F_k(r + 1))]$

My guesses are that:

1. Insecure, since an attacker A is not only given the ciphertext c, but also the key $r$ with which the message was encrypted. Thus, it can easily decrypt the ciphertext.

2. I would say that it's not IND-CPA secure, since it's deterministic. But how can I prove/determine whether it's IND-COA secure? I would usually do proof a by contraposition, but I don't know how to start.

3. I have no idea whether this scheme is IND-COA or IND-CPA secure, since I don't know whether $(F_k(r) \; | \; F_k(r + 1))$ is a pseudorandom function.

Any hints or ideas? I appreciate any help!

• "Could A maybe learn [...] how the generator G works?" Under Kerckhoff's principle, information about the algorithms used is assumed to be public and available to attackers. Dec 15 '15 at 21:33
• In 2 and 3, where does $k$ come from? Dec 15 '15 at 21:47
• @user595228: I just realized that myself and have changed the question accordingly! Dec 16 '15 at 8:03
• @fkraiem: k is chosen uniformly at random, $k \in \{0,1\}^n$ Dec 16 '15 at 8:06
• Then certainly 2 is not deterministic. However, how does the recipient decrypt? Is $k$ pre-shared? Dec 16 '15 at 8:07

1. This scheme does not have indistinguishable encryptions since the encryption function does not use the key, so an adversary can run the decryption function in the same way as the intended recipient.

2. This scheme is not CPA-secure because it is deterministic (so it does not even have indistinguishable encryptions for multiple messages). To show that it has indistinguishable encryptions for a single message, we first note that if $f$ is a random function, $f(0^n)$ is uniformly distributed and we get a one-time pad. Now, if a distinguisher $D$ can distinguish $m_0\oplus F_k(0^n)$ from $m_1\oplus F_k(0^n)$, we can distinguish $F_k$ from a random function as follows. A distinguisher $D'$ chooses at random $b\in \{0,1\}$ and runs $D$ on $m_b\oplus O_{D'}(0^n)$. $D'$ outputs $1$ if $D$ answers correctly, and $0$ otherwise. If $O_{D'}$ is a true random function, $D$ answers correctly with probability exactly $1/2$. On the other hand, if $O_{D'}$ is $F_k$ for a uniformly chosen $k$, then by hypothesis $D$ answers correctly with probability non-negligibly higher than $1/2$, which translates to a distinguishing advantage for $D'$.

3. This scheme is CPA-secure, try to apply the idea of the previous one to transform a distinguisher for the encryption scheme into a distinguisher for $F$.

• I don't see how 2. proves that the scheme is COA secure for a single message. Don't I have to explain somehow, that I can't distinguish $F_k$ from a truly random function? Otherwise I don't get a contradiction in the proof. Dec 16 '15 at 9:49
• The point is that if you can distinguish encryptions, then you can distinguish $F_k$ from a true random function, which contradicts the hypothesis that it is pseudorandom. Dec 16 '15 at 9:52
• Now I get it. Thanks! I learned a lot from this discussion. Dec 16 '15 at 9:58
1. Insecure, since an attacker A is not only given the ciphertext $c$, but also the key $r$ with which the message was encrypted. Thus, it can easily decrypt the ciphertext.

Correct, there is no encryption here.

1. I would say that it's not IND-CPA secure, since it's deterministic. Is that true? And how can I prove/determine whether it's IND-COA secure? I would usually do proof by contraposition, but I don't know how to start.

Since it is deterministic, it cannot be IND-CPA, but it is worse than that. This is at least as insecure as the many-time pad. Every message encrypted with the same key is XORed with the same value.

1. I have no idea whether this scheme is IND-COA or IND-CPA secure, since I don't know whether $(F_k(r) \; | \; F_k(r + 1))$ is a pseudorandom function.

This is equivalent to using CTR mode with $F_k$ as a PRF, which is IND-CPA secure (and thus COA).

• But even the many-time pad is secure in the IND-COA game (as described in the comments). What this actually shows: How bad the IND-COA definition is.
– tylo
Nov 4 '16 at 17:40