Ternary Syndrome Decoding with Large Weight
This work addresses a fundamental problem in cryptography for designing more secure code-based cryptosystems, though it is incremental as it builds on existing concepts.
The paper tackles the ternary Syndrome Decoding problem with large weight, a key issue in code-based cryptography, by conducting an algorithmic study that leads to updated parameters for the Wave signature scheme and demonstrates it is significantly harder than the binary version.
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.