Beam Search for Solving Substitution Ciphers
Malte Nuhn, Julian Schamper, Hermann Ney · RWTH Publications (RWTH Aachen) · 2013
In this paper we address the problem of solving substitution ciphers using a beam search approach.We present a conceptually consistent and easy to implement method that improves the current state of the art for decipherment of substitution ciphers and is able to use high order n-gram language models.We show experiments with 1:1 substitution ciphers in which the guaranteed optimal solution for 3-gram language models has 38.6% decipherment error, while our approach achieves 4.13% decipherment error in a fraction of time by using a 6-gram language model.We also apply our approach to the famous Zodiac-408 cipher and obtain slightly better (and near to optimal) results than previously published.Unlike the previous state-of-the-art approach that uses additional word lists to evaluate possible decipherments, our approach only uses a letterbased 6-gram language model.Furthermore we use our algorithm to solve large vocabulary substitution ciphers and improve the best published decipherment error rate based on the Gigaword corpus of 7.8% to 6.0% error rate.