Attacking Decipherment Problems Optimally with Low-Order N-gram Models

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 812–819, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Attacking Decipherment Problems Optimally with Low-Order N-gram Models Sujith Ravi and Kevin Knight University of Southern California Information Sciences Institute Marina del Rey, California 90292 {sravi,knight}@isi.edu Abstract We introduce a method for solving substi- tution ciphers using low-order letter n-gram models. This method enforces global con- straints using integer programming, and it guarantees that no decipherment key is over- looked. We carry out extensive empirical ex- periments showing how decipherment accu- racy varies as a function of cipher length and n-gram order. We also make an empirical in- vestigation of Shannon’s (1949) theory of un- certainty in decipherment. 1 Introduction A number of papers have explored algorithms for automatically solving letter-substitution ciphers. Some use heuristic methods to search for the best de- terministic key (Peleg and Rosenfeld, 1979; Gane- san and Sherman, 1993; Jakobsen, 1995; Olson, 2007), often using word dictionaries to guide that search. Others use expectation-maximization (EM) to search for the best probabilistic key using letter n-gram models (Knight et al., 2006). In this paper, we introduce an exact decipherment method based on integer programming. We carry out extensive de- cipherment experiments using letter n-gram models, and we find that our accuracy rates far exceed those of EM-based methods. We also empirically explore the concepts in Shan- non’s (1949) paper on information theory as applied to cipher systems. We provide quantitative plots for uncertainty in decipherment, including the famous unicity distance, which estimates how long a cipher must be to virtually eliminate such uncertainty. We find the ideas in Shannon’s (1949) paper rel- evant to problems of statistical machine translation and transliteration. When first exposed to the idea of statistical machine translation, many people natu- rally ask: (1) how much data is needed to get a good result, and (2) can translation systems be trained without parallel data? These are tough questions by any stretch, and it is remarkable that Shannon was already in the 1940s tackling such questions in the realm of code-breaking, creating analytic formulas to estimate answers. Our novel contributions are as follows: • We outline an exact letter-substitution deci- pherment method which: - guarantees that no key is overlooked, and - can be executed with standard integer pro- gramming solvers • We present empirical results for decipherment which: - plot search-error-free decipherment results at various cipher lengths, and - demonstrate accuracy rates superior to EM- based methods • We carry out empirical testing of Shannon’s formulas for decipherment uncertainty 2 Language Models We work on letter substitution ciphers with spaces. We look for the key (among 26! possible ones) that, when applied to the ciphertext, yields the most English-like result. We take “English-like” to mean 812 most probable according to some statistical lan- guage model, whose job is to assign some proba- bility to any sequence of letters. According to a 1- gram model of English, the probability of a plaintext p1...pn …

Content truncated to 500 words