Decipherment Complexity in 1:1 Substitution Ciphers
Malte Nuhn and Hermann Ney
The 51st Annual Meeting of the Association for Computational Linguistics (ACL 2013)
Sofia, Bulgaria, August 4-9, 2013
In this paper we show that even for the case of 1:1 substitution ciphers---which encipher plaintext symbols by exchanging 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 assignment problem (QAP). To the best of our knowledge, this connection between the QAP and the decipherment problem has not been known in the literature before.
Conference Manager (V2.61.0 - Rev. 2792M)