Cryptology ePrint Archive: Report 2019/304

Ternary Syndrome Decoding with Large Weight

Rémi Bricout and André Chailloux and 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.

Category / Keywords: public-key cryptography / public-key cryptography / code-based cryptography / Information set decoding / subset sum

Date: received 18 Mar 2019

Contact author: thomas debris at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20190320:103133 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]