Semantic Security and Equal Message Length in the Context of Public Key Cryptography

Question

A lot of definitions for semantic security make use an experiment $\text{Exp}$ which is performed between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}$ that begins as follows:

$\mathcal{C}$ generates a random key w.r.t. the considered cryptosystem and a given security parameter. $\mathcal{A}$ selects two messages $m_0$ and $m_1$ of the same bit length (i.e., $|m_0| = |m_1|$) and sends $m_0$ and $m_1$ to the adversary (and so on).

Now, assume that the considered cryptosystem is a public key cryptosystem. In $\text{Exp}$, $\mathcal{C}$ randomly chooses a public/private key pair $(sk,pk)$. Assume that the public key $pk$ is given to $\mathcal{A}$. Let $\mathbb{P}$ be the message space determined by $pk$.

The question is whether—for the given setting—$\text{Exp}$ remains valid if $\mathcal{A}$ chooses arbitrary plaintexts $m_0$, $m_1$ from $\mathbb{P}$ or, otherwise, is it still necessary that $|m_0| = |m_1|$ for $m_0,m_1 \in \mathbb{P}$ holds?

Answer 1

There are two styles of definition that deal with the issue of message "length" in different ways.

One style considers an encryption algorithm that is capable of encrypting bit strings of arbitrary length. Such an algorithm cannot completely hide the message length, for information-theoretic reasons. (Padding short messages to conceal their lengths doesn't overcome the problem; however much padding the algorithm uses, there are always longer messages that cannot fit into the same total length.) Therefore, in this context a definition of security should require that the adversary produce two messages of the same bit length.

A second style considers an encryption algorithm that is only well defined for messages that come from some finite "message space," which may depend on the security parameter or even the public key. For such algorithms, there's no inherent problem with message length, because all valid messages have a bounded "length" (or representation). In this context, the security definition need not require that the adversary's messages are of equal length; it should only require that the messages are both valid, i.e., that they belong to the message space. (If one message was invalid, the adversary could easily distinguish the two experiments because encryption fails in one and succeeds in the other.)

There are many examples of encryption schemes that fit into the second framework. Symmetric encryption of fixed-length messages using a (fixed output length) PRF is one. "Algebraic" cryptosystems like ElGamal or RSA, where the message space is some finite group $G$ or $\mathbb{Z}_n^*$ (respectively), are another. Systems like Goldwasser-Micali, where the message space is just $\{0,1\}$, are further examples.

Answer 2

No, the experiment does not remain valid because the ciphertext must leak some information about the length of the plaintext, so if the lengths of the two plaintexts in the indistinguishability experiment are not restricted, the adversary could choose plaintexts of suitable, different lengths and use the information leaked by the ciphertext to gain an advantage. It may be possible to impose a weaker condition than equality on the lengths of the plaintexts, but the usefulness of doing so is not evident since there has to be some condition. For example, a condition that they should not differ by more than some prescribed value would just make things more complicated than they already are.

For more on this, see the exercises in the chapter about encryption schemes in the book of Goldreich.