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?
2
-
$\begingroup$ 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). $\endgroup$– ponchoSep 26, 2016 at 18:19
-
$\begingroup$ 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 !! $\endgroup$– devSep 26, 2016 at 18:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
-
$\begingroup$ Thanks, you made things understandable by proving this ! $\endgroup$– devSep 26, 2016 at 19:25
$\begingroup$
$\endgroup$
2
As poncho already wrote in the comments, this isn't possible:
- Basically the only way to hide the length of a message is to use a padding, which is long enough.
- The adversary knows at least the encryption method and implicitly the length of the padding.
- If you allow arbitrary messages, he can choose one message really short (e.g. 1 bit) and the other longer than the padding. If your encryption scheme allows arbitrary length messages, this must be possible, e.g. by a mode of operation (known from block ciphers)
You can't adapt the padding length after seeing the messages chosen by the attacker. Otherwise the information about the length might leak other information about the message again, and then you're going in circles.
edit: Oh, and again you might want to explain notation and security games in the question - even if it doesn't actually matter for this one. Writing down clear definitions might help you see problems on your own.
-
$\begingroup$ thanks for you quick reply, I have just one question about the 3rd point, the encryption scheme allows arbitrary length messages, for fact, in this case doing a block ciphers could be one solution to make this happens? $\endgroup$– devSep 26, 2016 at 18:42
-
$\begingroup$ Using a mode of operation is one way to allow arbitrary length messages. The mode itself doesn't actually require a symmetric encryption. It could also be OTP or any public key cryptosystem, where you consider a arbitrary message as a sequence of blocks. The size of the blocks then depends on what message space your encryption method can handle. $\endgroup$– tyloSep 26, 2016 at 18:54