Mysteries Department
Sign inRequest access
MethodsCryptanalysisLattice EM on CUDA with batched restarts, basin hopping and parallel tempering, run up a ladder of planted controls (T44)
Method · cryptanalysis

Lattice EM on CUDA with batched restarts, basin hopping and parallel tempering, run up a ladder of planted controls (T44)

Session 12 showed the lattice-EM model is right on the simplest planted control (the true key's basin has the best likelihood, -40,505) but the search never reached it (best -40,836 after 400 restarts and 250 hops; coverage 0.407 against a bar of 0.483). Two cores limited the search to a few hundred restarts. This method asks whether search at GPU scale (5,000+ restarts, batched basin hopping, parallel tempering) reaches the basin, and if so how far up the difficulty ladder the key stays recoverable, before the manuscript is touched.

CryptanalysisVersion 1.0Licence MIT8 runsUsed on 1 mystery

Code Python

Download module (.py)lattice_gpu.pyView source

Runs and results 8 runs · 6 shown

RunMysteryMeasuredResultAgainstDate
RUN0DCM6AJ47G7GVoynichTraining log-likelihood, expected counts, decoded held-out text and held-out likelihood per glyph of the GPU port against lattice em.py (numba) on the one-sign-per-letter planted control; seconds per EM iterationfloat64: E-step from the true channel ll -42,115.3720 both, max |dC| 3.9e-12, max |dCn| 7e-14; seed-6205 restart -41,009.90 both (max |dB| 8e-15), decoded held-out text identical (5,929 characters), null-word share 0.262 both, held-out ll/glyph -1.9505 both. float32: ll -42,115.3711, seed 6205 -41,009.89, max |dB| 3e-6, text identical. Throughput: 1,024 restarts 1.27 s per EM iteration with the CUDA graph (3.9 s eager); 256 restarts 0.78 s. Session-12 seed 6205 on this machine: -40,975.8, -41,037.6, -41,009.9 (PYTHONHASHSEED=0, repeatable), -41,034.1 (1), against -40,851.8 on record; hash-independent: 871 signs, true-key ll -41,653.7, EM from truth -40,504.6, key 0.777 (record: -41,654, -40,505, 0.777)Session 12 generation 6 (RUN0DCHDDGSSB3H): seed 6205 -40,851.8 · diagnostic (RUN0DCG2Q30P808): true key -41,654, EM from truth -40,505
RUN0DCMW01CAK37VoynichBest training log-likelihood per search; held-out key accuracy by use, dictionary coverage (bar 0.7 x plaintext's = 0.483), character similarity, key-permutation p (200 permutations)restarts (5,000): best -40,788.8 (key 0.652; quantiles 0/10/50/90/99 %: -42,107 / -41,736 / -41,490 / -41,314 / -41,078); basin hopping from the top 16 (40 rounds x 1,024 proposals): -40,674.8 (key 0.736); parallel tempering from the same states (40 rounds x 1,024 chains, 8 temperatures): -40,698.6 (key 0.666). Decode of the best state: coverage 0.440 (permuted keys mean 0.266, max 0.371, p 0.005), character similarity 0.638, key 0.736, null words 0.154, held-out ll/glyph -1.9368. 'aterescontigititeporiseriasatundentiticunepiciqueiam...' for 'aberenoncontigitcumteporisarboresabundentibipunicaeficiqueiam...'Session 12: best of 400 restarts -40,852 (key 0.623), 250 hops -40,836 (key 0.691, coverage 0.407) · EM from the true key -40,514 on this inventory (coverage 0.518, key 0.778)
RUN0DCMW72CK8Y3VoynichHeld-out dictionary coverage of the planted control decoded with the true channel and with EM started from it, against the gate bar (0.7 x the true plaintext's coverage); bigram decoder (numba lattice em) and trigram decoder (lattice gpu3)bigram EM from truth: R1 0.518 (bar 0.483), R2 0.508 (0.487), R3 0.482 (0.488), R4 0.450 (0.488), R5 0.290 (0.262; vowel-less plaintext covers only 0.374); key 0.78-0.84 throughout. Trigram Viterbi of the true channel: R1 0.584, R2 0.585, R3 0.544, R4 0.513, R5 0.275; character similarity 0.74-0.84 (R5 0.58). Trigram EM from the truth (10-14 iterations) keeps these within 0.01, except R5 where the factored trigram (22 history classes) drifts to 0.242. A near-random key (accuracy 0.11) decoded by the trigram Viterbi still reaches coverage 0.524 (permuted keys 0.475): coverage alone cannot be the gate under this decoderSession 12 ceiling (RUN0DCG56XXNDPT): one sign per letter 0.518, full T39 setting 0.441 with the bigram decoder
RUN0DCNEZ6RMXGRVoynichBest training log-likelihood per search (bigram), trigram likelihood after polish; held-out key accuracy by use, dictionary coverage (bar 0.7 x plaintext's = 0.483), character similarity, key-permutation p (200 permutations, trigram decoder)restarts (5,000, seeds 200000+): -40,772.8 (key 0.687); hopping 80 rounds x 1,024: -40,675.9 (key 0.737; stalled after round 55); tempering 20 rounds: -40,724.4 (key 0.687). Trigram polish of the 5 best states (30 iterations): trigram lls -39,848 / -39,831 / -39,868 / -39,850 / -39,838; the chosen state's key 0.737. Trigram decode: coverage 0.489 (permuted keys mean 0.339, max 0.432, p 0.005), character similarity 0.673, null words 0.142, held-out ll/glyph -1.8916. The same state decoded by the bigram Viterbi: coverage 0.413. 'ecereporisercusacundenticipunaciliqueiammalispirimaudatisimaeprigideseodemtratumgenuitercuspinumacie' for 'aberenoncontigitcumteporisarboresabundentibipunicaeficiqueiammalietpirilaudatisimaefrigidaseodemtrac'Generation 1 (RUN0DCMW01CAK37): -40,674.8, key 0.736, bigram-decoded coverage 0.440 · true key: trigram-decoded coverage 0.584, key 0.778 · session 12's best: key 0.691, coverage 0.407
RUN0DCP774CN9D7VoynichBest training log-likelihood per search; trigram likelihood after polish; held-out key accuracy by use, dictionary coverage (bar 0.7 x plaintext's = 0.487), character similarity, key-permutation p (200 permutations, trigram decoder)1,205 signs. Restarts (5,000): -48,200.0 (key 0.624; median -48,753); hopping 80 rounds: -48,041.3 (key 0.656; stalled from round 50); tempering 20 rounds: -48,098.1 (key 0.608). Trigram polish of 5 states: -47,850.1 / -47,850.7 / -47,869.5 / -47,927.2 / -47,881.3; chosen state's key 0.673. Trigram decode: coverage 0.468 (permuted keys mean 0.320, max 0.409, p 0.005), character similarity 0.537, null words 0.175, held-out ll/glyph -2.021; bigram decode of the bigram-best state 0.392. 'namiceraeomneatraepictasagenimenumarelagonfueraperarinunto...' for 'nevitibusquidemxivceteraeomnesextrapraedictasetenimenumerarelongumestfoliadeperduntobservatumque...'True key on R2: bigram EM from truth -47,587 (key 0.845), trigram-decoded coverage 0.581 · R1 generation 2 passed at key 0.737, coverage 0.489
RUN0DCQ48MV18VHVoynichBest training log-likelihood (bigram) and trigram likelihood after polish; held-out key accuracy by use, dictionary coverage (bar 0.487), character similarity, key-permutation p (200 permutations, trigram decoder)restarts (5,000, seeds 400000+): -48,119.1 (key 0.403); hopping with the mixed move set, 150 rounds x 1,024: -47,740.4 (key 0.694; still moving at round 149: -47,866 at 70, -47,772 at 80, -47,752 at 120). Trigram polish of 8 states (60 iterations): best -47,429.4 (from the bigram best; the others -47,542 to -47,944). Trigram decode: coverage 0.466 (permuted keys mean 0.326, max 0.417, p 0.005), character similarity 0.591, null words 0.173, held-out ll/glyph -2.0159; bigram decode 0.388. 'nateraeomneaedinfecetenimenumerarelonpumatroineaerinuntobseretum...' for 'nevitibusquidemxivceteraeomnesextrapraedictasetenimenumerarelongumestfoliadeperduntobservatumque...'Generation 1 of R2 (RUN0DCP774CN9D7): -48,041.3, key 0.673, coverage 0.468 · true key: -47,587 (bigram), key 0.845, trigram-decoded coverage 0.581

Applied to

Voynich Manuscript
5 datasetsHerbal A and Herbal B paragraph text: training and held-out pages, Latin genre texts, Line-edge rules learned on half E (46 minimal alternations at paragraph start, line start and line end), Naibbe cipher tables and example plaintexts (greshko/naibbe-cipher, commit 719f2f4c), Token table

References

  1. Aldarrab, N., May, J. 2022. Segmenting Numerical Substitution Ciphers.
  2. Berg-Kirkpatrick, T., Klein, D. 2013. Decipherment with a Million Random Restarts. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing.
  3. Journal of the Physical Society of Japan 65(6): 1604-1608 (J-STAGE page checked). Parallel tempering (replica exchange). Track B candidate key search to compare with Lasry-style annealing.
  4. Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pp. 499-506 (ACL Anthology page checked). EM decipherment: a fixed plaintext n-gram model and a learned channel P(cipher sign | plaintext letter), trained by forward-backward. Base of the Track A lattice EM method.
Private beta Downloads are for beta members

We're in a private beta while we get things right. Everything here is free to read; downloading datasets, sources and code is open to members for now.

Apply to the betaSign in
It takes a couple of minutes. We'll reply by email.