Determine if encryption is safe against CPA

Question

The following encryption scheme encrypts each block of length $n$ of the plaintext separately:

$c_i = k_1 \oplus F(k_2 \oplus p_i)$

Where $F$ is a strong pseudo-random permutation (i.e. it is easy to calculate $F(.)$ and $F^{-1}(.)$), and $|k_1|=|k_2|=n$.

$a.$ Is this encryption safe against a CPA attack with a single block? multiple blocks?

$b.$ Show an efficient attack to discover the two keys.

So I thought of choosing $p=0$, and then we easily get $k_1 \oplus F(k_2)$, and we can do the same with $p=1$. But then we have two equations with our two variables being $k_1$ and $F(k_2)$, so we can get $k_1$, but how does that help with $k_2$ if we cannot calculate $F^{-1}$?

Am I in the right direction? Any help would be appreciated.

Answer 1

With multiple blocks the scheme is definitely not CPA as the same plaintext blocks encrypt to the same ciphertext. Using the security game given here as a framework for proving this, begin by letting $m_0 = 0^n0^n1^n$ and $m_1 = 0^n1^n0^n$. Given back a ciphertext $c = Enc_{k1, k2}(m_i)$ (where $i \in \{0, 1\}$) we can look at blocks two and three of $c$ to determine $i$. If the second block of $c$ is equal to the first block then $i = 0$. If the third block of $c$ is equal to the first block then $i = 1$. So the adversary can always correctly determine which plaintext was encrypted.

My thought on one block is that the scheme is CPA, though I don't quite know how to prove it. Assuming that $F$ is a strong PRP we can say that $F(.) \approx U_n$ ($U_n$ being uniform randomness). Given this, we can say that $c \approx k_1 \oplus U_n \approx U_n$. This intuitively indicates to me that encrypting only one block is CPA secure.

I'm not sure how to recover the keys efficiently, given that (if I remember correctly) by definition the probability of efficiently inverting a strong PRP is $< \epsilon(n)$ (aka negligible). That means getting anything back out of $F$ should not be feasible.