Decipherment of Substitution Ciphers with Neural Language Models

Nishant Kambhatla, Anahita Mansouri Bigvand, Anoop Sarkar


Abstract
Decipherment of homophonic substitution ciphers using language models is a well-studied task in NLP. Previous work in this topic scores short local spans of possible plaintext decipherments using n-gram language models. The most widely used technique is the use of beam search with n-gram language models 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 language model. We augment beam search with a novel rest cost estimation that exploits the prediction power of a neural language model. 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.
Anthology ID:
D18-1102
Volume:
Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing
Month:
October-November
Year:
2018
Address:
Brussels, Belgium
Editors:
Ellen Riloff, David Chiang, Julia Hockenmaier, Jun’ichi Tsujii
Venue:
EMNLP
SIG:
SIGDAT
Publisher:
Association for Computational Linguistics
Note:
Pages:
869–874
Language:
URL:
https://aclanthology.org/D18-1102
DOI:
10.18653/v1/D18-1102
Bibkey:
Cite (ACL):
Nishant Kambhatla, Anahita Mansouri Bigvand, and Anoop Sarkar. 2018. Decipherment of Substitution Ciphers with Neural Language Models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 869–874, Brussels, Belgium. Association for Computational Linguistics.
Cite (Informal):
Decipherment of Substitution Ciphers with Neural Language Models (Kambhatla et al., EMNLP 2018)
Copy Citation:
PDF:
https://aclanthology.org/D18-1102.pdf
Video:
 https://aclanthology.org/D18-1102.mp4