2
$\begingroup$

I am currently working on the following task:

Let F be a pseudorandom permutation.

  1. Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses two random keys $k_1 , k_2 \in \{0, 1\}^n$. Encryption is done as $Enc_{k_1,k_2}(m) = F_{k1}( k_2 \oplus m)$ (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

  1. Consider the encryption scheme where the message space is $\{0, 1\}^{n/2}$ and encryption of a message $m$ is done by choosing random $r \leftarrow \{0, 1\}^{n/2}$ , and then outputting the ciphertext $F_k(r ||m)$. (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

My current answers are:

  1. This scheme has indistinguishable encryptions in the presence of an eavesdropper since $F$ is a PRP, and therefore $F_{k1}( k_2 \oplus m)$ will give a pseudorandom string. However I am not sure whether my intuition is correct. The scheme should not be IND-CPA secure since encryption is deterministic.

  2. This scheme is both IND-COA as well as IND-CPA secure. IND-COA since (as in 1.) $F$ is a PRP, and therefore $F_k(r ||m)$ will give a pseudorandom string. It's also IND-CPA secure as a random $r$ is used every time a message in encrypted.

Since I am not too confident about my solutions I appreciate any comments and/or corrections.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Maybe if you tried to actually prove your answers you would be more confident in them. :) $\endgroup$
    – fkraiem
    Mar 12 '16 at 12:26
  • $\begingroup$ How does one decrypt in these schemes? $\endgroup$
    – Chris Peikert
    Mar 12 '16 at 12:31
  • $\begingroup$ @ChrisPeikert: The task only says that decryption is done in the natural way. I have added it in the question. $\endgroup$
    – Lemon
    Mar 12 '16 at 13:48
  • $\begingroup$ @fkraiem Actually, I don't know how. That the first scheme is not IND-CPA secure follows from the theorem that deterministic encryption schemes cannot be CPA secure. But what about the IND-COA security? I would usually try to show that if the scheme is not IND-COA secure then there exists some distinguisher that can tell $F_k$ apart from a random function. But for that I first have to be sure that $F_{k_1}(k_2 \oplus m)$ is as much a pseudorandom string as any other output of F_{k_1}. $\endgroup$
    – Lemon
    Mar 12 '16 at 14:02
  • 1
    $\begingroup$ @Lemon: I don't see a "natural" decryption algorithm, if $F$ is merely a PRF -- it may not be efficiently invertible, even given the key. If $F$ is a block cipher then decryption is natural. $\endgroup$
    – Chris Peikert
    Mar 12 '16 at 17:24
1
$\begingroup$

Looks rather OK to me.

As for the first question, XOR with a value won't introduce any duplicate values and now $F$ is a PRP the first part of the answer should be correct. It's clearly deterministic, so no IND-COA or CPA security.

As for the second question $F_k(r ||m)$ seems to me identical to a single block encrypt with CTR mode. However, for CTR mode you require quite a large block size.

You could well distinguish between $m=0$ and $m=1$ given enough ciphertext; you'd get a lot of 00 and 10 results if $m=0$ is prevalent, which would be different from the 01 and 11 results. Concatenation in general should be considered dangerous.

So I think it could be CPA secure, but only when $n$ is somewhere around 128 bits or higher and/or the amount of messages is restricted. Without additional restrictions the answer should be no IND-COA or CPA security. Learning that a particular value is prevalent is already enough to break IND-COA:

e.g from Wikipedia about ciphertext-only attacks:

The ability to obtain any information at all about the underlying plaintext beyond what was pre-known to the attacker is still considered a success.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It's good to not be too confident. Hopefully, if I'm wrong some more theoretically inclined cryptographer will poncho holes in my reasoning. $\endgroup$
    – Maarten Bodewes ♦
    Mar 13 '16 at 15:32
  • $\begingroup$ Freud would have loved that “…will poncho holes…”. ;) $\endgroup$
    – e-sushi
    Jun 11 '16 at 20:11
  • $\begingroup$ @e-sushi Didn't take long for him to poncho a hole in my latest answer :P $\endgroup$
    – Maarten Bodewes ♦
    Jun 11 '16 at 20:50
  • $\begingroup$ Maybe bad karma? Chances are, you scared some fishes while kayaking today… =þ $\endgroup$
    – e-sushi
    Jun 11 '16 at 21:36
  • $\begingroup$ @e-sushi Nah, we've got "cute" seals to do that for us. Saw one today, swimming some 4 m from my kayak, looking directly at me with those black eyes. Sometimes seals play with the kayaks, but when they have young they can actually attack them as well. Someone actually had one of them jump on board I've heard, which makes it kinda unstable.... But we're buggering Lemon... $\endgroup$
    – Maarten Bodewes ♦
    Jun 11 '16 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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