Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Any messages from the plaintext space, bit lengths do not have to be the same. – mikeazo Oct 21 '15 at 12:51

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.

share|improve this answer
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 '15 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 '15 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 '15 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 '15 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 '15 at 13:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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