Decipherment Complexity in 1:1 Substitution Ciphers

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 615–621, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Decipherment Complexity in 1:1 Substitution Ciphers Malte Nuhn and Hermann Ney Human Language Technology and Pattern Recognition Computer Science Department, RWTH Aachen University, Aachen, Germany <surname>@cs.rwth-aachen.de Abstract In this paper we show that even for the case of 1:1 substitution ciphers—which encipher plaintext symbols by exchang- ing them with a unique substitute—finding the optimal decipherment with respect to a bigram language model is NP-hard. We show that in this case the decipherment problem is equivalent to the quadratic as- signment problem (QAP). To the best of our knowledge, this connection between the QAP and the decipherment problem has not been known in the literature be- fore. 1 Introduction The decipherment approach for MT has recently gained popularity for training and adapting trans- lation models using only monolingual data. The general idea is to find those translation model parameters that maximize the probability of the translations of a given source text in a given lan- guage model of the target language. In general, the process of translation has a wide range of phenomena like substitution and reorder- ing of words and phrases. In this paper we only study models that substitute tokens—i.e. words or letters—with a unique substitute. It therefore serves as a very basic case for decipherment and machine translation. Multiple techniques like integer linear program- ming (ILP), A∗ search, genetic algorithms, and Bayesian inference have been used to tackle the decipherment problem for 1:1 substitution ciphers. The existence of such a variety of different ap- proaches for solving the same problem already shows that there is no obvious way to solve the problem optimally. In this paper we show that decipherment of 1:1 substitution ciphers is indeed NP-hard and thus ex- plain why there is no single best approach to the problem. The literature on decipherment provides surprisingly little on the analysis of the complexity of the decipherment problem. This might be re- lated to the fact that a statistical formulation of the decipherment problem has not been analyzed with respect to n-gram language models: This paper shows the close relationship of the decipherment problem to the quadratic assignment problem. To the best of our knowledge the connection between the decipherment problem and the quadratic as- signment problem was not known. The remainder of this paper is structured as follows: In Section 2 we review related work. Section 3 introduces the decipherment problem and describes the notation and definitions used throughout this paper. In Section 4 we show that decipherment using a unigram language model corresponds to solving a linear sum assignment problem (LSAP). Section 5 shows the connection between the quadratic assignment problem and de- cipherment using a bigram language model. Here we also give a reduction of the traveling sales- man problem (TSP) to the decipherment problem to highlight the additional complexity in the deci- pherment problem. 2 Related Work In recent years …

Content truncated to 500 words