3
$\begingroup$

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”).

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ! $\endgroup$ – SyndicatorBBB Apr 5 '13 at 15:20
  • 1
    $\begingroup$ @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.) $\endgroup$ – Paŭlo Ebermann Apr 5 '13 at 16:37
  • $\begingroup$ @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 ! $\endgroup$ – SyndicatorBBB Apr 6 '13 at 16:29
  • $\begingroup$ @PaŭloEbermann "how large is the set of the corresponding ciphertexts?" I'm really curious of what assumptions are made to give a numerical bound to this. What would be the answer to this question and why? $\endgroup$ – Javier Nov 17 '18 at 15:11
  • $\begingroup$ @PaŭloEbermann also see the answer below. i appreciate your feedback $\endgroup$ – Javier Nov 17 '18 at 16:59
1
$\begingroup$

The solution proposed in Katz and Lindell for this goes along these lines.

Let $q(n)$ be a polynomial upper-bound on the length of the ciphertext when $\Pi$ is used to encrypt a single bit, i.e., if $b$ is a bit, $c = Enc_k(b)$ then $|c| \le q(n)$. Note that this is a reasonable assumption since, our encryption system's algorithms work in polynomial time. Therefore, their input should also be polynomial (in the size of the security parameter).

Now, one considers an adversary who outputs $m_0 \in \{0,1\}$ and a uniform $m_1 \in \{0,1\}^{q(n)+2}$. Then, one can use Paŭlo Ebermann suggestions to reason like this. We have $2^{q(n)+2}$ possible plaintexts for $m_1$. We have less than $2 + 2^2 + \ldots + 2^{q(n)} = 2^{q(n)+1} - 1 \le 2^{q(n)+1}$ ciphertexts for our single bit .

Then, one has to ask how many of our $2^{q(n)+2}$ plaintexts could possibly encrypt to the $2^{q(n)+1}$ ciphertexts. Here we may note that no two messages should encrypt to the same cyphertext, since normally one sets the condition $Dec_k(Enc_k(m)) = m$. It is clear that this is a fraction $\frac{2^{q(n)+1} - 1}{2^{q(n)+2}} < \frac{1}{2}$. This would tell that $q = P[|Enc_k(m_1)| > q(n)] > \frac 1 2$ and $P[|Enc_k(m_1)| \le q(n)] < \frac 1 2$.

Now, the attacker could work as follows:

$A(c) = \begin{cases} 1 & \text{ if } |c| > q(n) \\ 0 & \text{ if } |c| \le q(n) \end{cases}$

Then the winning probability is:

$P[Win] = \frac 1 2 \Big(P[r = 1|c = Enc_k(m_1)] + P[r = 0|c = Enc_k(m_0)]\Big) = \frac 1 2 \Big(q + 1\Big) > \frac 3 4$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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