Ternary Syndrome Decoding with Large Weight

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

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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
public-key cryptography
Contact author(s)
thomas debris @ inria fr
History
2019-06-14: revised
See all versions
Short URL
https://ia.cr/2019/304

CC BY

BibTeX

@misc{cryptoeprint:2019/304,
author = {Rémi Bricout and André Chailloux and Thomas Debris-Alazard and Matthieu Lequesne},
title = {Ternary Syndrome Decoding with Large Weight},
howpublished = {Cryptology ePrint Archive, Paper 2019/304},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/304}},
url = {https://eprint.iacr.org/2019/304}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.