From Entropy's perspective how Encryption affects a Message?

Question

How Ciphers, specifically, Substitution Ciphers and Transposition Ciphers manipulate the Entropy of Plaintext w/wo the aid of Entropy Source?

Reversely, how Decryption manipulates the entropy of Ciphertext?

Link: From Entropy's perspective how a Message was affected by Entropy, specifically, One-time Pad Ciphers and Block Ciphers?

Answer 1

Everything I say here are completely theoretical, not backed by any research, and are completely opinions.

There are 2 kinds of complexity we consider here:

• Data complexity: this is studied by Shannon in his seminal paper "The Mathematical Theory of Communication".

• Process complexity: there are different ways to categorize it, such as

  1. complexity classes: L, P, NP, RE, etc.
  2. Kolmogorov complexity: the "amount of information" needed to describe the process as an algorithm which is able to produce a certain output.
  3. closely related to Kolmogorov complexity, which I call "learning complexity". In essence, it's the overall complexity (memory x time x code size) to recover a certain knowledge, such as the plaintext corresponding to some ciphertext, or an encryption key.

  Let's label them as following: 1 is generic, 2 is generative, 3 is determinative.

So back to the question. An cipher makes it hard to learn a plaintext, therefore, encryption is a categorization-2 process that (somehow, one way or another) increases the data complexity of a message, so as to make a categorization-3 process costly for adversaries; likewise, decryption is the categorization-3 process that recovers the plaintext - when the key is known, it's less complex, when the key is unknown, it's more complex.

---

Now that Q's been clarified that discussion on substitution and transposition ciphers is desired, here it goes:

Statistically, substitution cipher doesn't add much data complexity to the message if any at all, since substitutions are just one-to-one mappings. _{If the substitution alphabet is large, say 128-bit blocks, then it may be interesting if subsequent substitution is dependent on previous states, like AES-CBC cipher.}

Transposition ciphers on the other hand, breaks original statistical relationship between consecutive characters. In particular, if we model the production of text as a Markov chain, then transposition severely break that chain.

Answer 2

The source of entropy in encryption schemes is the secret key. Substitution and transposition ciphers are not secure methods of encryption because they are vulnerable to frequency analysis attacks. They also have a small key space.

The weakest modern security notion for encryption is security in the presence of an eavesdropper. The adversary is presented with a ciphertext $c$ which is an encryption of either $m_0$ or $m_1$ where both are chosen by the adversary itself, and it must produce a guess for which message was encrypted. The encryption scheme is secure if the adversary's probability of guessing is not much better than the trivial $\frac 12$.

In this setting, the messages $m_0$ and $m_1$ both have no entropy from the adversary's point of view, since it chooses them. But the ciphertext $c$ has large entropy since the adversary does not know the secret key which was used to generate it.