Decipherment of Substitution Ciphers with Neural Language Models
Nishant Kambhatla, Anahita Mansouri Bigvand, Anoop Sarkar · 2018
Decipherment of homophonic substitution ciphers using language models (LMs) is a wellstudied task in NLP.Previous work in this topic scores short local spans of possible plaintext decipherments using n-gram LMs.The most widely used technique is the use of beam search with n-gram LMs proposed by Nuhn et al. (2013).We propose a beam search algorithm that scores the entire candidate plaintext at each step of the decipherment using a neural LM.We augment beam search with a novel rest cost estimation that exploits the prediction power of a neural LM.We compare against the state of the art n-gram based methods on many different decipherment tasks.On challenging ciphers such as the Beale cipher we provide significantly better error rates with much smaller beam sizes.