Historical ciphers, when they were introduced and their effect

[kckluge]

2) Introduce nulls.

• Some extra characters in the ciphertext don't correspond to anything. This can be used to obscure the most frequent characters, break up common bigrams etc. 
  
• Existed before the 15th century (?)
  
• Effects: larger glyph set, increased entropy (sometimes or always?)
  

--> even LESS like Voynichese

3) Homophonic cipher

• Each plaintext letter can be replaced by multiple ciphertext symbols. Hides frequency -> harder to crack
  
• Existed before the 15th century (?)
  
• Effects: larger glyph set; I would expect higher entropy but I'm not sure.
  

--> even LESS like Voynichese

In the case of nulls entropy can at least *potentially* decrease (consider the reductio ad absurdum case where 99% of the text is a single null character, although the Copiale may well be a real world example).

In the case of homophones, I believe the following is a correct proof that the 1st order entropy must be higher than that of the underlying text:

* Consider the contribution of letter 'x' to the entropy, p(x) * -log(p(x))

* Without loss of generality, represent 'x' in the cipher with two homophones 'y' and 'z', so p(y) + p(z) = p(x) --> p(y) = p(x) - p(z)

* For p(x) > p(z) > 0, -log(p(z)) and -log(p(x) - p(z))   >   -log(p(x))

* -log(p(z)) > -log(p(x)) --> p(z) * -log(p(z))   >   p(z) * -log(p(x))

* -log(p(x) - p(z)) > -log(p(x)) --> (p(x) - p(z)) * -log(p(x) - p(z))   >   (p(x) - p(z)) * -log(p(x))

* --> (p(x) - p(z)) * -log(p(x) - p(z)) + p(z) * -log(p(z))   >   (p(x) - p(z)) * -log(p(x)) + p(z) * -log(p(x))

* --> (p(x) - p(z)) * -log(p(x) - p(z)) + p(z) * -log(p(z))   >   p(x) * -log(p(x))

I'm pretty sure that proof should generalize to the unconditional 2nd order entropy, but I'd have to think longer and harder than I'm prepared to do at the moment to see if there's a proof that the conditional 2nd order entropy must also be larger...