I know that, for any CPA-secure public-key encryption scheme, the size of the ciphertext after encrypting a single bit is superlogarithmic in the security parameter. That is, for $(pk,sk) \leftarrow Gen(1^n)$ it must hold that $|Enc_{pk}(b)| = w(\log n)$ for any $b \leftarrow \{0,1\}$.

The problem is that I took it as a heuristic, thus I don't know the big "WHY". So, finally, why and how can I show that?

  • $\begingroup$ Count how many possible encryptions of 0 there are if the size is $O(\log n)$ and likewise for 1. Then, use this information to carry out an attack. $\endgroup$ – Yehuda Lindell Aug 26 '15 at 19:37
  • $\begingroup$ @YehudaLindell If the ciphertext size of one bit only is logarithmic in $n$, then there are $2^{w(\log n)}$ possible ciphertexts for either $1$ or $0$ as plaintext. The encryption scheme($\Pi$) is supposed to be CPA-secure, thus it is randomized. This means that given the $PPT$ adversary $A$ the challenge ciphertext $c=Enc_{pk}(b)$, in order for $A$ to break $\Pi$: $Pr[PubK^{cpa}_{A,\Pi}(n)=1] \geq 1/2 + negl(n)$, and here I'm stuck. $\endgroup$ – pa5h1nh0 Aug 27 '15 at 13:37
  • 1
    $\begingroup$ If the ciphertext of one bit is only logarithmic in $n$, then there exists a constant $c$ such that it is of size at most $c\cdot \log n$. Thus, there are $2^{c\cdot\log n} = n^c$ possibilities. $\endgroup$ – Yehuda Lindell Aug 28 '15 at 5:57

Your Answer

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

Browse other questions tagged or ask your own question.