Not-So-Simple Substitution Cipher?

Question

The first go-to weakness when talking about substitution ciphers is frequency analysis. It assumes that there's a simple 1 to 1 character mapping between the plain text and the cipher text.

Could a frequency analysis be thwarted if this were a 1 to Many mapping?

For example, what if the input text contained say 30 characters: 26 letters, space, period, question mark, and exclamation mark. Enough for most communication needs between two people. The output could be quite a bit larger, like the 95 printable characters. E could be mapped to multiple output characters that appear at unusual frequencies in the cipher text that don't look like E on a frequency analysis. This mapping could also map space to 1 or more characters so you can't analyze word length or word frequency.

Every character could map to at least 3 output characters and knowing that some characters are already pretty rare they may not even need to be mapped to that many. Perhaps just 2 or even 1 that way other more frequently used characters could map to 5 or 6 cipher text characters.

Is there a different kind of analysis that could target a cipher like this?

Answer 1

This is called homophonic encryption, and has been around for a long time.

In terms of cryptanalysis of such ciphers, there is a nice thesis from SJSU on this topic which is available here. The attacks tested in that cipher were based on hill climbing and local optimization techniques. The conclusion states:

We designed and implemented an efficient attack on the homophonic substitution ciphers. The attack is based on the hill-climbing heuristic technique. The proposed algorithm has a multi-layered architecture with three nested loops to solve the challenges imposed by the homophonic substitution ciphers and the hill-climbing technique. The algorithm was successfully tested on simple substitution ciphers and many instances of homophonic substitution ciphers with variable ciphertext sizes and cipher symbol sizes. [..] For the ciphertexts having minimum 3000 characters and maximum 75 cipher symbols, the algorithm was able to break at least 85% of cipher symbols.

So, homophonic substitution increases the required ciphertext length, as expected, for a high rate of success of correctly decrypting plaintext characters. If 55 ciphertext symbols are used (to flatten the frequency distribution) the success rate increases from about 10% for a ciphertext length of 300 characters to about 80% for a ciphertext length of 4000 characters.

If 95 ciphertext characters are used, at 4000 character ciphertext length, the success rate is around 50%.