Segmenting Numerical Substitution Ciphers

Nada Aldarrab, Jonathan May


Abstract
Deciphering historical substitution ciphers is a challenging problem. Example problems that have been previously studied include detecting cipher type, detecting plaintext language, and acquiring the substitution key for segmented ciphers. However, attacking unsegmented ciphers is still a challenging task. Segmentation (i.e. finding substitution units) is essential for cracking those ciphers. In this work, we propose the first automatic methods to segment those ciphers using Byte Pair Encoding (BPE) and unigram language models. Our methods achieve an average segmentation error of 2% on 100 randomly-generated monoalphabetic ciphers and 27% on 3 real historical homophonic ciphers. We also propose a method for solving non-deterministic ciphers with existing keys using a lattice and a pretrained language model. Our method leads to the full solution of the IA cipher; a real historical cipher that has not been fully solved until this work.
Anthology ID:
2022.emnlp-main.44
Volume:
Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing
Month:
December
Year:
2022
Address:
Abu Dhabi, United Arab Emirates
Editors:
Yoav Goldberg, Zornitsa Kozareva, Yue Zhang
Venue:
EMNLP
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
706–714
Language:
URL:
https://aclanthology.org/2022.emnlp-main.44
DOI:
10.18653/v1/2022.emnlp-main.44
Bibkey:
Cite (ACL):
Nada Aldarrab and Jonathan May. 2022. Segmenting Numerical Substitution Ciphers. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 706–714, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Cite (Informal):
Segmenting Numerical Substitution Ciphers (Aldarrab & May, EMNLP 2022)
Copy Citation:
PDF:
https://aclanthology.org/2022.emnlp-main.44.pdf