tailieunhanh - Báo cáo khoa học: "Bayesian Inference for Zodiac and Other Homophonic Ciphers"

We introduce a novel Bayesian approach for deciphering complex substitution ciphers. Our method uses a decipherment model which combines information from letter n-gram language 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 decipherment output on simple and homophonic letter substitution ciphers and show that unlike a previous approach, our method consistently produces almost 100% accurate decipherments. . | Bayesian Inference for Zodiac and Other Homophonic Ciphers Sujith Ravi and Kevin Knight University of Southern California Information Sciences Institute Marina del Rey California 90292 sravi knight @ Abstract We introduce a novel Bayesian approach for deciphering complex substitution ciphers. Our method uses a decipherment model which combines information from letter n-gram language 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 decipherment output on simple and homophonic letter substitution ciphers and show that unlike a previous approach our method consistently produces almost 100 accurate decipherments. 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 fashion which has never been done before. 1 Introduction Substitution ciphers have been used widely in the past to encrypt secrets behind messages. These ciphers replace English plaintext letters with cipher symbols in order to generate the ciphertext sequence. There exist many published works on automatic decipherment methods for solving simple lettersubstitution ciphers. Many existing methods use dictionary-based attacks employing huge word dictionaries to find plaintext patterns within the ciphertext Peleg and Rosenfeld 1979 Ganesan and Sherman 1993 Jakobsen 1995 Olson 2007 . Most of these methods are heuristic in nature and search for the best deterministic key during deci 239 pherment. Others follow a probabilistic decipherment approach. Knight et al. 2006 use the Expectation Maximization EM algorithm Dempster et al. 1977 to search for the best probabilistic key using letter n-gram models. Ravi and Knight 2008 formulate decipherment as an integer programming problem and provide an exact method to solve simple substitution ciphers by using letter n-gram models along with .