Take the 2-minute tour ×

I need your help with a very basic concept in cryptography which I can't understand/prove on my own.

I'm trying to prove and understand why, under "indistinguishability in the presence of an eavesdropper" encrpytion, it is required that the lengths of the messages output by the adversary satisfy $|m_0| = |m_1|$.

Just to make sure the reader understand exactly what's I'm talking about, the context of my question is page 6 of these lecture notes on Constructing a Computationally Secure Scheme Pseudorandomness (“Claim of indistinguishable encryptions in the presence of an eavesdropper”).

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Well, the problem is that -- as long as your encryption algorithm accepts messages of arbitrary length -- it is impossible to hide the length of the encrypted message.

This is actually quite natural. Think about it, when I encrypt a 1000 bit message I simply need more bits to represent the ciphertext than when I encrypt only a single bit.

Therefore, if one of the messages is allowed to be longer than the other, it is in general quite easy to distinguish between the two cases, because in the one case the ciphertext will be longer.

share|improve this answer
It does help me a lot, thank you. I just need a little more help on the prove, see :cse.ohio-state.edu/~lai/5351/Homework%203-sp13.pdf (question 1). I found out a complete guideline (cs.wellesley.edu/~cs310/ps/ps4.pdf - problem 2) and yet I can't see how the prove for this goes by using pigeonhole argument. Can you please help me understand it a little bit from the prove aspect. Thank you very much ! –  SyndicatorBBB Apr 5 '13 at 15:20
@SyndicatorBBB What is the size of the set of plaintexts of size $q(n)+2$? So, how large is the set of the corresponding ciphertexts? How large is the set of messages of size $\leq q(n)$? So a how big fraction of the "long plaintexts" can encrypt to a "short ciphertext"? So how big is the probability of getting a larger ciphertext? (You don't need exact numbers for each, often inequalities are enough.) –  Paŭlo Ebermann Apr 5 '13 at 16:37
@PaŭloEbermann thank you very much. The answer of Maeher together with your thought questions leads me to the conclusion that I can't answer this question with the material which was learnt in the classroom. I will try to use it after an appointement with the teacher to understand why these tought questions are important and how to prove it. Thank you both for all the help ! –  SyndicatorBBB Apr 6 '13 at 16:29

Your Answer


