1 Search Results for "Portoleau, Tom"


Document
On How Turing and Singleton Arc Consistency Broke the Enigma Code

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

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{antuori_et_al:LIPIcs.CP.2021.13,
  author =	{Antuori, Valentin and Portoleau, Tom and Rivi\`{e}re, Louis and Hebrard, Emmanuel},
  title =	{{On How Turing and Singleton Arc Consistency Broke the Enigma Code}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.13},
  URN =		{urn:nbn:de:0030-drops-153040},
  doi =		{10.4230/LIPIcs.CP.2021.13},
  annote =	{Keywords: Constraint Programming, Cryptography}
}
  • Refine by Author
  • 1 Antuori, Valentin
  • 1 Hebrard, Emmanuel
  • 1 Portoleau, Tom
  • 1 Rivière, Louis

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Combinatoric problems

  • Refine by Keyword
  • 1 Constraint Programming
  • 1 Cryptography

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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