# Encryption scheme with arbitrary length message

Is the definition $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi}^{eav}(n) = 1] \leq \frac{1}{2} + negl(n)$ still valid in case we have an encryption scheme $\pi (Gen,Enc,Dec)$ with arbitrary length, and the adversary $\mathcal A$ is not outputting equal length messages?

• That wouldn't appear to be possible; the adversary could choose two messages, a 1 bit message, and a huge $N$ byte random message. Then, unless your encryption scheme pads out the 1 bit message to $> N$ bytes, the adversary would be able to distinguish (and given that $N$ is allowed to be arbitrarily large, this would appear to be impossible). – poncho Sep 26 '16 at 18:19
• So this $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi}^{eav}(n) = 1] \leq \frac{1}{2} + negl(n)$ won't be valid in my case right? but I don't know how to make proof of it !! – dev Sep 26 '16 at 18:29

Here's a way of demonstrating a specific distinguisher (that's a bit more precise than tylo's talk about padding).

First, ask for the encryption of two identical 1 bit messages; record the length of the ciphertext. Do it 100 times, and call the length of the longest ciphertext you see $N$ (obviously, as the encryption method is randomized, the ciphertext length is allowed to vary).

Then, generate a random $N+10$ bit length message $M$, and ask for the encryption $M$, and the 1 bit message you used previously. Look at the length of the resulting ciphertext; if it is $\le N$, say it's the encryption of the 1 bit message, if it's $> N$, then say it's message $M$.

If the Oracle selected the 1 bit message, this distinguisher will output 'it's the 1 bit message' with probability $> 0.99$ (as that's the probability that this encryption is not longer than the previous 100 encryptions of an identical ciphertext). If the Oracle selected the N bit message, this distinguisher will output 'it's $M$' with probability $>1-2^{-10}$ (as that's the maximum probability that an invertible algorithm will be unable to shrink a random message by at least 10 bits).

• Thanks, you made things understandable by proving this ! – dev Sep 26 '16 at 19:25