How to construct a variable length IND-CPA cipher from a fixed length one?

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.

• Modes of operation are the way to do it. Oct 16, 2012 at 23:22
• 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). Oct 17, 2012 at 2:17

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.

• 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. Oct 17, 2012 at 7:23
• That's how the CPA game works. $\:$ (Otherwise no cipher could CPA-securely handle arbitrary input lengths.)
– user991
Oct 17, 2012 at 7:27
• 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?
– user4083
Oct 17, 2012 at 16:24
• @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. Oct 17, 2012 at 17:25

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.

• According to this and this, for the IND-CPA game, the messages are by definition of equal length. Where have you seen otherwise? Oct 17, 2012 at 17:18
• @mikeazo: The Wikipedia page about Ciphertext indistinguishability doesn't contain the word length, though this might be a mistake there. Oct 22, 2012 at 20:04
• @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. Oct 22, 2012 at 22:16