Decipherment Complexity in 1:1 Substitution Ciphers
Malte Nuhn, Hermann Ney · RWTH Publications (RWTH Aachen) · 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.