Paper: Bayesian Inference for Zodiac and Other Homophonic Ciphers

ACL ID P11-1025
Title Bayesian Inference for Zodiac and Other Homophonic Ciphers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2011
Authors

We introduce a novel Bayesian approach for deciphering complex substitution ciphers. Our method uses a decipherment model which combines information from letter n-gram lan- guage models as well as word dictionaries. Bayesian inference is performed on our model using an efficient sampling technique. We evaluate the quality of the Bayesian deci- pherment output on simple and homophonic letter substitution ciphers and show that un- like a previous approach, our method consis- tently produces almost 100% accurate deci- pherments. The new method can be applied on more complex substitution ciphers and we demonstrate its utility by cracking the famous Zodiac-408 cipher in a fully automated fash- ion, which has never been done before.