2022/05/25 by Nada Aldarrab, Jonathan May, Aldarrab, Nada +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning in Bioinformatics #Natural Language Processing Techniques #cs.CL
paper · pdf · doi:10.48550/arxiv.2205.12527
arxiv created 2022/05/25 · openalex publication_date 2022/05/25 · arxiv updated 2022/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, space-free ciphers is still a challenging task. Segmentation (i.e. finding substitution units) is the first step towards 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 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.