An Exact A* Method for Deciphering Letter-Substitution Ciphers

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1040–1047, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics An Exact A* Method for Deciphering Letter-Substitution Ciphers Eric Corlett and Gerald Penn Department of Computer Science University of Toronto {ecorlett,gpenn}@cs.toronto.edu Abstract Letter-substitution ciphers encode a docu- ment from a known or hypothesized lan- guage into an unknown writing system or an unknown encoding of a known writing system. It is a problem that can occur in a number of practical applications, such as in the problem of determining the encod- ings of electronic documents in which the language is known, but the encoding stan- dard is not. It has also been used in rela- tion to OCR applications. In this paper, we introduce an exact method for decipher- ing messages using a generalization of the Viterbi algorithm. We test this model on a set of ciphers developed from various web sites, and find that our algorithm has the potential to be a viable, practical method for efficiently solving decipherment prob- lems. 1 Introduction Letter-substitution ciphers encode a document from a known language into an unknown writ- ing system or an unknown encoding of a known writing system. This problem has practical sig- nificance in a number of areas, such as in reading electronic documents that may use one of many different standards to encode text. While this is not a problem in languages like English and Chinese, which have a small set of well known standard en- codings such as ASCII, Big5 and Unicode, there are other languages such as Hindi in which there is no dominant encoding standard for the writing system. In these languages, we would like to be able to automatically retrieve and display the in- formation in electronic documents which use un- known encodings when we find them. We also want to use these documents for information re- trieval and data mining, in which case it is impor- tant to be able to read through them automatically, without resorting to a human annotator. The holy grail in this area would be an application to ar- chaeological decipherment, in which the underly- ing language’s identity is only hypothesized, and must be tested. The purpose of this paper, then, is to simplify the problem of reading documents in unknown encodings by presenting a new algo- rithm to be used in their decipherment. Our algo- rithm operates by running a search over the n-gram probabilities of possible solutions to the cipher, us- ing a generalization of the Viterbi algorithm that is wrapped in an A* search, which determines at each step which partial solutions to expand. is guaranteed to converge on the language-model-It optimal solution, and does not require restarts or risk falling into local optima. We specifically con- sider the problem of finding decodings of elec- tronic documents drawn from the internet, and we test our algorithm on ciphers drawn from ran- domly selected pages of Wikipedia. Our testing indicates that our algorithm …

Content truncated to 500 words