Paper: Decipherment Complexity in 1:1 Substitution Ciphers

ACL ID P13-1060
Title Decipherment Complexity in 1:1 Substitution Ciphers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2013
Authors

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.