1
$\begingroup$

I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am stuck on the following problem.

Let $\mathcal{E}$ be be an encryption scheme where messages and ciphertexts are bit strings.

(a). Suppose that for all keys and all messages m, the encryption of m is the exact same length as m. Show that $(E,D)$ cannot be semantically secure under a chosen plaintext attack.

I would like a hint on this problem. I have tried thinking about ciphers which preserve length like the one time pad and stream ciphers, but I can only think of the attack which exploits the fact that those are deterministic. I am not sure what to do in the case $\mathcal{E}$ is not deterministic.

I would appreciate a hint on this problem.

Thanks!

$\endgroup$

2 Answers 2

2
$\begingroup$

I think this should work.

Note that no deterministic encryption scheme can be CPA secure; a simple attack is discussed in the book. Next, note that any probabilistic encryption scheme will result in ciphertext expansion, since an encryption of a single plaintext is one of multiple possible ciphertexts. Therefore any encryption scheme which preserves message length is deterministic and it follows that such a scheme will not be CPA secure by the attack discussed in the book.

$\endgroup$
2
  • 3
    $\begingroup$ Something along these lines should work. It is perhaps easier to mention that the fact that $\mathcal{E}$ preserves lengths can be rewritten as $\forall k \in\mathbb{N}, \mathcal{E}_{\mid k} : \{0,1\}^k\to\{0,1\}^k$ restricted to $k$-bit inputs is a bijection. Note that for any cryptosystem $\mathcal{E}_{\mid k} : \{0,1\}^k\to \mathcal{E}(\{0,1\}^k)$ must be an injection (so it decrypts correctly). As $\mathcal{E}$ preserves lengths we know that $\mathcal{E}(\{0,1\}^k) \subseteq \{0,1\}^k$, and it then follows that its a bijection. This implies that $\mathcal{E}$ is deterministic, and $\endgroup$
    – Mark Schultz-Wu
    Commented Jan 22, 2023 at 3:11
  • 2
    $\begingroup$ therefore insecure. $\endgroup$
    – Mark Schultz-Wu
    Commented Jan 22, 2023 at 3:11
0
$\begingroup$

Show that $(\mathcal{E},\mathcal{D})$ cannot be semantically secure under a chosen plaintext attack.

The simplest way to do this is via an attack. It is often easiest to rewrite these kinds of questions into "find an attack that does X", as that's actually your goal.

For this one in particular, the rewriting ends up being.

Let $(\mathcal{E}, \mathcal{D})$ be an encryption scheme such that $|\mathcal{E}(m)| =|m|$. Design an efficient adversary $\mathcal{A}$ that can recover the value of $b$ from the oracle $\mathcal{E}_b(m_0, m_1) := \mathcal{E}(m_b)$ with good advantage.

Feel free to ask for more hints in the comments, but this already seems a bit easier to approach (despite being a simple rewriting of your question).

$\endgroup$
5
  • $\begingroup$ Thanks for your reply. I meant to say in the original post that I'm not able to come up with an attack which yields good advantage. Can you give me a hint on what sort of queries I should think about as an adversary playing the CPA game? $\endgroup$ Commented Jan 21, 2023 at 1:18
  • $\begingroup$ in all the length preserving encryption schemes I have seen (eg one time pad, stream ciphers, block ciphers), the scheme is deterministic. So I am wondering if it is possible that any length preserving encryption scheme must be deterministic? If so, how can I show this? $\endgroup$ Commented Jan 21, 2023 at 2:15
  • $\begingroup$ One could potentially show this, but you are really overthinking it. Does $\mathcal{E}$ leak any explicit information about the ciphertexts? If so, can you query $\mathcal{E}_b(m_0, m_1)$ on different ciphertexts to exploit this? Consider the case of $|m_0|\neq |m_1|$ specifically. $\endgroup$
    – Mark Schultz-Wu
    Commented Jan 21, 2023 at 18:09
  • $\begingroup$ yes but I thought in the game between an adversary and a challenger defining CPA security, an adversary's queries can only be pairs of messages $m_0$ and $m_1$ where $|m_0| = |m_1|$. $\endgroup$ Commented Jan 21, 2023 at 21:48
  • $\begingroup$ @cryptolearner it depends on the formal definition of the game. Generally all that matters in practice is that the padded length of the messages (up to some common block size) is identical. But in your setting (of no padding) there could be messages $|m_0| = |m_1| + 1$ that have the same padded length (i.e. would take the same # of blocks to encrypt with a standard cryptosystem) but different actual lengths. $\endgroup$
    – Mark Schultz-Wu
    Commented Jan 22, 2023 at 3:07

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.