Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
1  
Modes of operation are the way to do it. – mikeazo♦ Oct 16 '12 at 23:22
1  
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). – Mikero Oct 17 '12 at 2:17

2 Answers

up vote 1 down vote

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.

share|improve this answer
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. – Paŭlo Ebermann♦ Oct 17 '12 at 7:23
1  
That's how the CPA game works. $\:$ (Otherwise no cipher could CPA-securely handle arbitrary input lengths.) – Ricky Demer Oct 17 '12 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 '12 at 16:24
1  
@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. – mikeazo♦ Oct 17 '12 at 17:25
up vote -2 down vote

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.

share|improve this answer
3  
According to this and this, for the IND-CPA game, the messages are by definition of equal length. Where have you seen otherwise? – mikeazo♦ Oct 17 '12 at 17:18
@mikeazo: The Wikipedia page about Ciphertext indistinguishability doesn't contain the word length, though this might be a mistake there. – Paŭlo Ebermann♦ Oct 22 '12 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. – mikeazo♦ Oct 22 '12 at 22:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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