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

---

Abstract

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.

---

START Conference Manager (V2.61.0 - Rev. 2792M)