Paper: Beam Search for Solving Substitution Ciphers

ACL ID P13-1154
Title Beam Search for Solving Substitution Ciphers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2013

In this paper we address the problem of solving substitution ciphers using a beam search approach. We present a concep- tually consistent and easy to implement method that improves the current state of the art for decipherment of substitution ci- phers 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 bet- ter (and near to optimal) results than pre- viously published. Unlike the previous state-of-the-art approach that uses addi- tional word lists to evalua...