Let $\Pi$ be a public-key encryption scheme. For every palintext $x \in \{0,1\}^{*}$, is there a PPT adversary $A$ such that $$\Pr \left[ 1^{|x|} \leftarrow A\left( pk, \mathrm{Enc}_{pk} (x) \right) \right] \geq 1 / poly \left( \lambda \right)$$ or even $$\Pr \left[ 1^{|x|} \leftarrow A\left( pk, \mathrm{Enc}_{pk} (x) \right) \right] \geq 1 - \varepsilon\left( \lambda \right)$$

Of course, if the plaintext space is finite (e.g. $\mathcal{P} = \{0,1\}^{m}$), it is not true. Here we assume that $\mathcal{P} = \{0,1\}^{*}$.

The definitions of many kinds of security (e.g. IND-CPA) have a condition that the test plaintexts must have the same length. Maybe, it implies that the ciphertext must preserve some information about the length of the plaintext. Is there a formal form about it?

  • $\begingroup$ By definition, you can say that the ciphertext $\operatorname{len}(C) \geq \operatorname{len}(P)$, so some information about the plaintext size is always known (assuming that $\operatorname{Enc}$ doesn't manage to compress the plaintext $P$). $\endgroup$ – Maarten Bodewes May 14 '18 at 15:06
  • $\begingroup$ The practical reason for the equal-length restriction in security definitions is to break schemes that are (except for some constant overhead) length-preserving, e.g. AES-GCM with a non-repeating nonce is CPA secure under standard definitions but if you allow variable length inputs, you can trivially distinguish a 1-byte from a 2-byte message. $\endgroup$ – SEJPM May 14 '18 at 17:37

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.