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.


1 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.

  • $\begingroup$ Thanks @puzzlepalace, that's a good example for why using this scheme for multiple blocks would enable an attacker to draw conclusions regarding the ciphertext. $\endgroup$
    – Cauthon
    Jun 22, 2015 at 11:48

Your Answer

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

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