DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.5

Satisfiability for Large Weight Syndrome Decoding

Authors: Carl Berton, Sami Cherif, and Claire Delaplace

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

The Large Weight Syndrome Decoding problem LWSD is a fundamental problem in coding theory. It consists in determining whether a given linear code admits a high Hamming weight vector associated with a specific syndrome. LWSD is a variant of the classical syndrome decoding problem, which conversely seeks a low Hamming weight solution for a linear system defined over the binary field 𝔽₂. In this paper, we investigate a generalization of this problem to the case of a prime finite field 𝔽_Z, referred to as LWZSD. We propose several models using Boolean Satisfiability (SAT) formulas and compare the efficiency of our approaches using state-of-the-art solvers.

Cite as

Carl Berton, Sami Cherif, and Claire Delaplace. Satisfiability for Large Weight Syndrome Decoding. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berton_et_al:LIPIcs.CP.2026.5,
  author =	{Berton, Carl and Cherif, Sami and Delaplace, Claire},
  title =	{{Satisfiability for Large Weight Syndrome Decoding}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.5},
  URN =		{urn:nbn:de:0030-drops-266385},
  doi =		{10.4230/LIPIcs.CP.2026.5},
  annote =	{Keywords: Large Weight Syndrome Decoding, Satisfiability, Cryptography}
}

Search Results

Documents authored by Berton, Carl

Satisfiability for Large Weight Syndrome Decoding

Abstract

Cite as

Thanks for your feedback!

Could not send message