0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ crypto.stackexchange.com/q/107869 Quotes fgrieu: It's not clear 1) Why the question is not a duplicate. 2) What "Entropy of Plaintext" is. Entropy is not a characteristic of data. It's a characteristic of a source of data. 3) "What "manipulate" means in the context. 4) Why the One-time Pad is considered a Cipher. By modern definition OTP is not a cipher, since a cipher must be able to encipher data repeatedly with the same key. 5) What is made to vary (Plaintext, key, IV) when considering the entropy of ciphertext; and, for plaintext, with what distribution. $\endgroup$
    – Schezuk
    Commented Sep 9, 2023 at 1:47

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It's over my head. Suppose that a string consisted of all zeros has minimum Kolmogorov complexity. If mixed with an equal length one-time pad, the entropy of ciphertext that can be measured will grow to the maximum value possible. In this process, isn't much data complexity added by substitution cipher? And doesn't decryption remove extra entropy? $\endgroup$
    – Schezuk
    Commented Sep 6, 2023 at 13:22
  • 1
    $\begingroup$ @Schezuk That's roughly the idea, except formulated in a less rigorous way. Also, one-time-pad isn't substitution cipher - substitution cipher uses a static mapping, where as mapping for each byte (or bit) is different (and independent of each other) for one-time-pad. $\endgroup$
    – DannyNiu
    Commented Sep 7, 2023 at 1:02
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ can i assume that entropy measures ignorance instead of knowledge which has zero entropy? $\endgroup$
    – Schezuk
    Commented Sep 7, 2023 at 0:35
  • 1
    $\begingroup$ Entropy measures the uncertainty we have about a random variable. If $X\in\{0,1\}^n$ has entropy $H(X)=0$, then $X$ is a deterministic value (always equal to some fixed $x$). On the other hand, if the entropy is high, then we have uncertainty on the value of $X$. In the case of maximal entropy of $n$ bit strings $H(X)=n$, the random variable $X$ is uniformly random. The same is true if we consider conditional entropy. If $H(X|Y)=0$, then this means that the value of $X$ is fully determined by the value of $Y$. In this case, $Y$ could represent the "knowledge" you have about $X$. $\endgroup$
    – lamontap
    Commented Sep 7, 2023 at 13:24

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.