Deck Cipher

A deck cipher is a general implementation of a Group Autokey (GAK) cipher mechanism with a convenient physical interpretation. This is not to be confused with existing ciphers that happen to use decks, like the solitaire cipher, and instead is a specific type of deck-based mechanism, one which produces perfect isomorphs.

Start with a deck of $n$ cards, one card for each letter of your ciphertext alphabet. For example, for the eyes, it would be a deck of 83 cards. Each card has a distinct label, which could be just an index, or some other naming convention or letters for the cards, it doesn't particularly matter, as long as all the symbols are distinct. Also choose some canonical ordering of the deck to be used as the initial state for encryption. The most natural choice for this is the standard sorted order, if the deck consists of indices from 0 to $n - 1$. Using a different initial state is equivalent to applying a substitution to the labels, so we can consider the initial state of the deck unshuffled without loss of generality.

Next, define a plaintext alphabet, consisting of some number of distinct symbols, e.g. A-Z or A-Z0-9. The plaintext alphabet needs to be less than or equal to the deck size in order for the cipher to be uniquely reversible, and it needs to be strictly less than the deck size if you want to deterministically avoid doubles.

For each letter of the plaintext alphabet, assign a permutation of the deck, or a shuffle, which should be applied when that plaintext letter is used in a message. The only restriction on the shuffles that can be chosen is that starting from an unshuffled state, each plaintext letter needs to bring a unique card to the top of the deck. This is required for reversibility of the cipher. Some kinds of shuffles that can be used include rotations (equivalent to "cutting the deck"), decimations (taking every $k$-th card), and swaps, and combinations of these. If you want to avoid doubles, all you need to do when choosing these shuffles is ensure that no plaintext letter causes a shuffle which leaves the top card of the deck unchanged, which is very easy to do.

To perform encryption of some plaintext message, start with the deck in the initial (unshuffled) state. At each step of encryption, look at the current plaintext letter, and apply the shuffle associated with that letter to the deck. Then use the label on the card that ended up at the top of the deck as the ciphertext output. Keep the deck in this shuffled state (including the card on top that was used for the ciphertext output), and advance to the next plaintext letter, continuing the same process until the entire message is encrypted.

Over the course of encryption, the deck becomes more and more shuffled, scrambling the state in a way that makes it extremely difficult to decrypt without knowing exactly what shuffles were used. If the shuffles are chosen completely arbitrarily, this cipher method ends up being equivalent to a GAK cipher with the underlying group being the symmetric group of all permutations of the cards, $S_n$, with the hidden subgroup being $S_{n-1}$. For an intuitive understanding of what makes it "hidden", consider that the top card of the deck is visible at each step as the ciphertext output. The remaining cards below that are in an unknown order unless you've been following the sequence of shuffles exactly, and these cards in an unknown order are the hidden state for this cipher.

There is something to be said about the massive key space of this cipher. If the shuffles are chosen completely randomly, there are $n!$ possible shuffles that can be chosen for each plaintext character. Really, this is restricted by a small amount because of the unique reversibility constraints, but the space is still enormous, especially considering the plaintext alphabet size may not be known for a puzzle where you are only given the ciphertext and no other information, like the eyes. The number of keys is so large that it might as well be comparable to a one-time pad (aside from the fact that we have the same mechanism used 9 times, so of course it couldn't technically be called a one-time pad).

The good news is that there is considerable evidence that the permutations are not completely random, and there is actually a somewhat simple structure to them. The main evidence for this comes from the shared sections after a differing first character. In a GAK cipher, assuming that first character is actually part of the message, this seems to only be possible if the permutations associated with the plaintext letters in the cipher are all relatively close to each other, in terms of only being a few swaps away from each other from some shared base permutation.