3
$\begingroup$

I have the following definition (highlights by me):

An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$, where $Gen$ and $Enc$ are PPT algorithms and $Dec$ is a Deterministic Polytime Algorithm, is one-time computationally-secret if for any PPT adversary $A$ it holds that the probability of the following experiment is negligibly biased from $1/2$:

  1. The adversary outputs two messages $m_0$ and $m_1$ of the same length.
  2. Let $k \leftarrow Gen(1^n)$ and let $b \in {0,1}$ be chosen uniformly at random. $c \leftarrow Enc_k(m_b)$ is computed and given to $A$
  3. A outputs the bit $b'$
  4. The output of the experiment is 1 $\iff b'=b$

I wonder why $m_0$ and $m_1$ should be of the same length, why is better than considering a non-fixed length encryption scheme?

The only drawback that comes to my mind is that if you are able to know something about the encryption of two messages of different length before they are actually encrypted (note that the key is generated in Step 2) then it would justify the choice of fixed-lenght. But I cannot think of a reason why it must be so.

Any ideas?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The encryption scheme in the experiment you describe does not have to be fixed-length. We simply require that the two messages the adversary sends to its oracle have the same length. The restriction is on the adversary, not on the encryption algorithm.

So why do we put this requirement on the adversary? The reason is that in every practical encryption scheme, ciphertexts leak information about the length of the corresponding plaintexts --- the longer the plaintext, the longer the ciphertext. So cryptographers basically threw their hands up in the air and said, "Fine, we'll just concede that length-information leaks. Can we make sure no other information leaks?" Requiring the lengths of $m_0$ and $m_1$ to be the same ensures that the adversary can't guess which one was enrypted simply by looking at the length of the ciphertext it gets back. Therefore the experiment you describe measures an adversary's ability to find some other way that information leaks.

Improve this answer
$\endgroup$
3
$\begingroup$

You had your finger on it, you do know something about the encryption of two messages of different length before they are actually encrypted: the length of the corresponding ciphertexts.

If the setting in which you're using your encryption scheme allows for a maximum message length then you can always pad to make every ciphertext the same size (!inneficient!) but otherwise, since encryption is supposed to be a invertible, longer plaintext means longer ciphertext. This means that you would have a trivial distinguisher in the security definition if you allowed messages of different length.

This ended up being longer that I intended it, to be but to sum it up: If you want to make sure you understood you should try to convince yourself that CBC encryption is very distinguishable in the security definition you want.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I am not sure about the part of the length of the corresponding ciphertext: note that in the Definition I gave above the Encryption algorithm $Enc$ is a PPT algorithm, therefore we know that $\forall n$ (security parameter) $\forall m$, $||Enc(m)|| < l(||k||+||m||)$, where $l(x) \in \mathbb{Z}[X]$, so we know that the length (i.e. the number of bits, denoted by $||\cdot||$ ) is polynomially bounded, so I don't think we can say that we know the length of the corresponding ciphertext... $\endgroup$
    – Alan Bletchley
    Commented Oct 24, 2012 at 19:10
  • $\begingroup$ @AlanBletchley Yes, there might be efficient secret-key encryption schemes according to your definition where the length of the ciphertext depends on the plaintext contents (not just it lengths), but you can prove that these can't be one-time computationally-secret (since the adversary then could use two plaintexts which give different ciphertext lengths, and distinguish them by this property). $\endgroup$
    – Paŭlo Ebermann
    Commented Oct 24, 2012 at 19:38
  • $\begingroup$ @AlanBletchley: In most practical schemes, the length of the ciphertext depends deterministically on the length of the plaintext, and there will exist at least two plaintexts that, with probability 1, map to ciphertexts with different lengths. You can certainly find counterexamples (Alexandre gives one based on padding). But defining the security of an algorithm in a way that prevents length information from leaking excludes many useful, otherwise secure algorithms. The security definition in your question is useful and "good enough" for most contexts. $\endgroup$
    – Seth
    Commented Oct 24, 2012 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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