Ternary Syndrome Decoding with large weight

DOI10.1007/978-3-030-38471-5_18zbMATH Open1453.94064arXiv1903.07464OpenAlexW3003672243MaRDI QIDQ778941FDOQ778941

Rémi Bricout, Matthieu Lequesne, André Chailloux, Thomas Debris-Alazard

Publication date: 21 July 2020

Abstract: The Syndrome Decoding problem is at the core of many code-based cryptosystems. In this paper, we study ternary Syndrome Decoding in large weight. This problem has been introduced in the Wave signature scheme but has never been thoroughly studied. We perform an algorithmic study of this problem which results in an update of the Wave parameters. On a more fundamental level, we show that ternary Syndrome Decoding with large weight is a really harder problem than the binary Syndrome Decoding problem, which could have several applications for the design of code-based cryptosystems.

Full work available at URL: https://arxiv.org/abs/1903.07464

Recommendations

• Time-memory tradeoffs for large-weight syndrome decoding in ternary codes
• An algorithm for generalized syndrome decoding problem
• Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
• scientific article; zbMATH DE number 1759341
• Analysis of information set decoding for a sub-linear error weight

zbMATH Keywords

post-quantum cryptographysubset sum algorithmsSyndrome Decoding problem

Mathematics Subject Classification ID

Cryptography (94A60)

Cited In (14)

• Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes
• Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
• An algorithm for generalized syndrome decoding problem
• Tight and optimal reductions for signatures based on average trapdoor preimage sampleable functions and applications to code-based signatures
• Improved classical and quantum algorithms for subset-sum
• Memory-efficient attacks on small LWE keys
• Low memory attacks on small key CSIDH
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice
• Information set decoding for Lee-metric codes using restricted balls
• Wave Parameter Selection
• Memory-efficient attacks on small LWE keys
• Generic error SDP and generic error CVE
• Improved information set decoding algorithms over Galois ring in the Lee metric
• Analysis of (U,U+V)-code problem with Gramian over binary and ternary fields

This page was built for publication: Ternary Syndrome Decoding with large weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778941)