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

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?

-
Any messages from the plaintext space, bit lengths do not have to be the same. – mikeazo Oct 21 at 12:51

## 1 Answer

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.

-
In my question, I assumed that the lengths of the two plaintexts are restricted in that they are both chosen from $\mathbb{P}$ where $\mathbb{P}$ is fixed by $pk$. – Zalander Oct 21 at 13:36
What is $P$, the plaintext space? Then it equals the set of all strings, unless you define encryption schemes differently than I do. – fkraiem Oct 21 at 13:39
For a public key cryptosystem with a public modulus $n$, the plaintext space is defined as $\mathbb{P} := \mathbb{Z}_n$. – Zalander Oct 21 at 13:49
Sorry, but what you are probably thinking about (the so-called "plain RSA") is not a cryptosystem. I suggest you consult a serious cryptography book, such as that of Katz and Lindell. – fkraiem Oct 21 at 13:56
@fkraiem, well, ElGamal is one example of a proper cryptosystem where something similar would be true. Some padded RSA algorithms, too. – otus Oct 21 at 13:58