2

Solitaire is a method for encrypting messages by hand. Reading it though, the only advantage the Solitaire has over a one time pad is that it can encrypt longer messages. It requires a new, random key for each message, just like OTP. In fact, schneir even recommends you keep messages short, limiting the length advantage.

However, the fact that a key is stored in a deck does limit the length quite a bit. A deck can only hold about 225 bits of information. OTP can only send messages smaller than the key. If you are encoding your message using, say, ASCII, that's only about 28 characters.

However, English has been empirically measured to have only 1 bit of entropy per character. That means that, after compression, you could send a 225 character message!

My question is, what are some methods to compress English that you can do by hand? It should be able to work on short messages, although you may assume the sender and receiver have some sort of shared state that could help. This state is allowed to be calculated using a computer before hand.

EDIT: As a clarification, it should be possible to compress any message, and get the exact message back when you decompress (i.e. we aren't considering lossy compression).

One method I thought of was to create a Huffman encoding where the symbols are English words, and provide the encoder and decoder with a dictionary for the codes of each word. Perhaps even better and more general would be a something based on finite state machines. The encoder and decoder would have separate state machines. To encode a message, it passed through the encoding machine which then spits out a code. To decode, the code is passed through the decoding machine which then spits out the original message. (Note that code here means "compressed message", not "encrypted message". Encryption is a separate process.) The finite state machines could be found using a computer, presumably, and represented via a large (book sized) table.

PyRulez
  • 2,937
  • 4
  • 15
  • 29
  • 4
    While the question is asked in the context of information security it essentially only cares about the compression of English text - which by itself is not a topic of information security. Therefore I'm voting to close this question as off-topic. – Steffen Ullrich Feb 14 '19 at 23:59
  • [Related](https://crypto.stackexchange.com/questions/1653/what-is-the-most-secure-hand-cipher) – PyRulez Feb 14 '19 at 23:59

1 Answers1

-1

You could probably have the highest compression ratio with a predefined dictionary. It could go as far as mapping a single compressed bit¹ to hundreds of pages detailing the war plans for the army.

If your scenario involves a couple of spies, they could communicate using a code book with a few keywords, on a simplified language. On the other hand, if they were writers exchanging their new novels, they would be very unhappy about any shade getting lost through the encryption layer.

¹ The error rate would be extremely high, though

Ángel
  • 17,578
  • 3
  • 25
  • 60
  • "It could go as far as mapping a single compressed bit to hundreds of pages detailing the war plans for the army." Unless literally *half* the messages are that exact set of war plans, that would be a terrible compression ratio. – PyRulez Feb 15 '19 at 00:10
  • @PyRulez: yes, I was thinking the message would either be "Don't attack yet" or "attack doing all these things". The amount of English compressed would be quite high, although it wouldn't allow for compressing arbitrary texts. :-) – Ángel Feb 15 '19 at 00:19
  • That is essentially the same as having an infinite compression ratio (from the point of view of loseless compression), since most messages get no code at all. – PyRulez Feb 15 '19 at 00:20