Search Results

Documents authored by Libralesso, Luc

Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2022.73
Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)

Authors: Florian Fontan, Pascal Lafourcade, Luc Libralesso, and Benjamin Momège

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.
Cite as

Florian Fontan, Pascal Lafourcade, Luc Libralesso, and Benjamin Momège. Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 73:1-73:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fontan_et_al:LIPIcs.SoCG.2022.73,
  author =	{Fontan, Florian and Lafourcade, Pascal and Libralesso, Luc and Mom\`{e}ge, Benjamin},
  title =	{{Local Search with Weighting Schemes for the CG:SHOP 2022 Competition}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{73:1--73:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.73},
  URN =		{urn:nbn:de:0030-drops-160811},
  doi =		{10.4230/LIPIcs.SoCG.2022.73},
  annote =	{Keywords: heuristics, vertex coloring, digital geometry}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.40
Automatic Generation of Declarative Models For Differential Cryptanalysis

Authors: Luc Libralesso, François Delobel, Pascal Lafourcade, and Christine Solnon

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

Abstract
When designing a new symmetric block cipher, it is necessary to evaluate its robustness against differential attacks. This is done by computing Truncated Differential Characteristics (TDCs) that provide bounds on the complexity of these attacks. TDCs are often computed by using declarative approaches such as CP (Constraint Programming), SAT, or ILP (Integer Linear Programming). However, designing accurate and efficient models for these solvers is a difficult, error-prone and time-consuming task, and it requires advanced skills on both symmetric cryptography and solvers. In this paper, we describe a tool for automatically generating these models, called Tagada (Tool for Automatic Generation of Abstraction-based Differential Attacks). The input of Tagada is an operational description of the cipher by means of black-box operators and bipartite Directed Acyclic Graphs (DAGs). Given this description, we show how to automatically generate constraints that model operator semantics, and how to generate MiniZinc models. We experimentally evaluate our approach on two different kinds of differential attacks (e.g., single-key and related-key) and four different symmetric block ciphers (e.g., the AES (Advanced Encryption Standard), Craft, Midori, and Skinny). We show that our automatically generated models are competitive with state-of-the-art approaches. These automatically generated models constitute a new benchmark composed of eight optimization problems and eight enumeration problems, with instances of increasing size in each problem. We experimentally compare CP, SAT, and ILP solvers on this new benchmark.
Cite as

Luc Libralesso, François Delobel, Pascal Lafourcade, and Christine Solnon. Automatic Generation of Declarative Models For Differential Cryptanalysis. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{libralesso_et_al:LIPIcs.CP.2021.40,
  author =	{Libralesso, Luc and Delobel, Fran\c{c}ois and Lafourcade, Pascal and Solnon, Christine},
  title =	{{Automatic Generation of Declarative Models For Differential Cryptanalysis}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{40:1--40:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.40},
  URN =		{urn:nbn:de:0030-drops-153314},
  doi =		{10.4230/LIPIcs.CP.2021.40},
  annote =	{Keywords: Constraint Programming, SAT, ILP, Differential Cryptanalysis}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2021.63
Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Authors: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.SoCG.2021.63,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc},
  title =	{{Shadoks Approach to Low-Makespan Coordinated Motion Planning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.63},
  URN =		{urn:nbn:de:0030-drops-138622},
  doi =		{10.4230/LIPIcs.SoCG.2021.63},
  annote =	{Keywords: heuristics, motion planning, digital geometry, shortest path}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact