Paper: Attacking Decipherment Problems Optimally with Low-Order N-gram Models

ACL ID D08-1085
Title Attacking Decipherment Problems Optimally with Low-Order N-gram Models
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2008
Authors

We introduce a method for solving substi- tution ciphers using low-order letter n-gram models. This method enforces global con- straints using integer programming, and it guarantees that no decipherment key is over- looked. We carry out extensive empirical ex- periments showing how decipherment accu- racy varies as a function of cipher length and n-gram order. We also make an empirical in- vestigation of Shannon’s (1949) theory of un- certainty in decipherment.