On How Turing and Singleton Arc Consistency Broke the Enigma Code

Authors Valentin Antuori, Tom Portoleau, Louis Rivière, Emmanuel Hebrard



PDF
Thumbnail PDF

File

LIPIcs.CP.2021.13.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Valentin Antuori
  • Renault, LAAS-CNRS, Université de Toulouse, CNRS, France
Tom Portoleau
  • LAAS-CNRS, Université de Toulouse, CNRS, France
Louis Rivière
  • LAAS-CNRS, Université de Toulouse, CNRS, ANITI, France
Emmanuel Hebrard
  • LAAS-CNRS, Université de Toulouse, CNRS, ANITI, France

Cite AsGet BibTex

Valentin Antuori, Tom Portoleau, Louis Rivière, and Emmanuel Hebrard. On How Turing and Singleton Arc Consistency Broke the Enigma Code. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.13

Abstract

In this paper, we highlight an intriguing connection between the cryptographic attacks on Enigma’s code and local consistency reasoning in constraint programming. The coding challenge proposed to the students during the 2020 ACP summer school, to be solved by constraint programming, was to decipher a message encoded using the well known Enigma machine, with as only clue a tiny portion of the original message. A number of students quickly crafted a model, thus nicely showcasing CP technology - as well as their own brightness. The detail that is slightly less favorable to CP technology is that solving this model on modern hardware is challenging, whereas the "Bombe", an antique computing device, could solve it eighty years ago. We argue that from a constraint programming point of vue, the key aspects of the techniques designed by Polish and British cryptanalysts can be seen as, respectively, path consistency and singleton arc consistency on some constraint satisfaction problems.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Constraint Programming
  • Cryptography

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Chris Christensen. Polish Mathematicians Finding Patterns in Enigma Messages. Mathematics Magazine, 80(4):247-273, 2007. URL: http://www.jstor.org/stable/27643040.
  2. Cipher A. Deavours and Louis Kruh. The Turing Bombe: Was it Enough? Cryptologia, 14(4):331-349, 1990. Google Scholar
  3. Romuald Debruyne and Christian Bessiere. Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI), 1997. Google Scholar
  4. Pascal Van Hentenryck and Jean-Philippe Carillon. Generality versus Specificity: An Experience with AI and OR Techniques. In Proceedings of the 7th National Conference on Artificial Intelligence (AAAI), 1988. Google Scholar
  5. Wladyslaw Kozaczuk. Enigma. How the German Machine Cipher Was Broken, and how It Was Read by the Allies in World War II. University Publications of America, 1984. Google Scholar
  6. Alan K. Mackworth. Consistency in Networks of Relations. In Bonnie Lynn Webber and Nils J. Nilsson, editors, Readings in Artificial Intelligence, pages 69-78. Morgan Kaufmann, 1981. URL: https://doi.org/10.1016/B978-0-934613-03-3.50009-X.
  7. Ugo Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7:95-132, 1974. URL: https://doi.org/10.1016/0020-0255(74)90008-5.
  8. Charles Prud'homme, Jean-Guillaume Fages, and Xavier Lorca. Choco Solver Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S., 2016. URL: http://www.choco-solver.org.
  9. Wikipedia contributors. Enigma rotor details, 2021. URL: https://en.wikipedia.org/wiki/Enigma_rotor_details.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail