Score:1

Crypto

Showing that CPA encryption schemes cannot preserve the length of a message

cryptolearner

1/21/24, 12:11 AM

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!

2 + 0

provable-security

chosen-plaintext-attack

indistinguishability

Score:2

Crypto

cryptolearner

1/21/24, 2:32 AM

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.

+ 2

Mark

1/22/24, 3:11 AM

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

Mark

1/22/24, 3:11 AM

therefore insecure.

Score:0

Crypto

Mark

1/21/24, 12:22 AM

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).

+ 5

cryptolearner

1/21/24, 1:18 AM

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?

cryptolearner

1/21/24, 2:15 AM

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?

Mark

1/21/24, 6:09 PM

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.

cryptolearner

1/21/24, 9:48 PM

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|$.

Mark

1/22/24, 3:07 AM

@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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Showing that CPA encryption schemes cannot preserve the length of a message

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.