2
$\begingroup$

Suppose we can construct a secure (IND-CPA) encryption scheme for fixed length messages. I was wondering if there is a natural way to extend this construction for messages of variable length such that it is still an IND-CPA secure scheme.

$\endgroup$
2
  • 1
    $\begingroup$ Modes of operation are the way to do it. $\endgroup$
    – mikeazo
    Oct 16 '12 at 23:22
  • 1
    $\begingroup$ You don't need modes of operation if you already have IND-CPA security (they're designed for pseudorandom functions). If you already have IND-CPA security, you can encrypt a long message bitwise and concatenate the resulting ciphertexts (analogous to ECB mode). $\endgroup$
    – Mikero
    Oct 17 '12 at 2:17
2
$\begingroup$

The typical way to make an encryption scheme work for variable length message is to use a mode of operation.

Since you are starting with an already IND-CPA secure cipher, even the often despised ECB mode will work. That said, you will still need padding to make the plaintext length a multiple of the blocksize. If adding padding is out of the question, a streaming mode such as CTR will work.

$\endgroup$
4
  • $\begingroup$ This works only if the attacker in the CPA-game can only submit two same-size (or "same size after padding") messages, as otherwise one can simply distinguish them by ciphertext length. $\endgroup$ Oct 17 '12 at 7:23
  • 2
    $\begingroup$ That's how the CPA game works. $\:$ (Otherwise no cipher could CPA-securely handle arbitrary input lengths.) $\endgroup$
    – user991
    Oct 17 '12 at 7:27
  • $\begingroup$ Okay, I understand the padding. Thus because the length of the padded message is a multiple of the blocksize, and for each "block" we already know that the encryption is secure, the eventual concatenation of encrypted "blocks" is secure? Is this correct? And how would you prove something like this? $\endgroup$
    – user4083
    Oct 17 '12 at 16:24
  • 1
    $\begingroup$ @Thom, assume the variable length scheme is not IND-CPA secure. From there, it shouldn't be too hard to show that the single-block version is also not IND-CPA secure. That is a contradiction, so the variable length scheme must be IND-CPA secure. $\endgroup$
    – mikeazo
    Oct 17 '12 at 17:25
-2
$\begingroup$

If you want a real variable length, you loose the IND-CPA security:

You have to make all possible ciphertexts equally long, so that the attacker can not distinguish between the longest possible message and a 1 bit message. If maximum length is not known at the key generation, your ciphertexts would need unlimited length.

If you allow the attacker to know the message length (this isn't IND-CPA anymore), you can choose any kind of encoding (e.g. blockwise or arithmetically) and apply encryption on each part individually.

$\endgroup$
3
  • 3
    $\begingroup$ According to this and this, for the IND-CPA game, the messages are by definition of equal length. Where have you seen otherwise? $\endgroup$
    – mikeazo
    Oct 17 '12 at 17:18
  • $\begingroup$ @mikeazo: The Wikipedia page about Ciphertext indistinguishability doesn't contain the word length, though this might be a mistake there. $\endgroup$ Oct 22 '12 at 20:04
  • $\begingroup$ @Paulo, right, I noticed that too, which is why I linked to the semantic security page instead. The second link is probably the more authoritative of the two. $\endgroup$
    – mikeazo
    Oct 22 '12 at 22:16

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.