Ternary Syndrome Decoding with Large Weight

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

doi:10.1007/978-3-030-38471-5_18

Ternary Syndrome Decoding with Large Weight

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers
Editors	Kenneth G. Paterson, Douglas Stebila
Publisher	Springer
Pages	437-466
Number of pages	30
ISBN (Print)	9783030384708
DOIs	https://doi.org/10.1007/978-3-030-38471-5_18
Publication status	Published - 1 Jan 2020
Event	26th International Conference on Selected Areas in Cryptography, SAC 2019 - Waterloo, Canada Duration: 12 Aug 2019 → 16 Aug 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11959 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on Selected Areas in Cryptography, SAC 2019
Country/Territory	Canada
City	Waterloo
Period	12/08/19 → 16/08/19

Keywords

Post-quantum cryptography
Subset sum algorithms
Syndrome decoding problem

Access to Document

10.1007/978-3-030-38471-5_18

Cite this

Bricout, R., Chailloux, A., Debris-Alazard, T., & Lequesne, M. (2020). Ternary Syndrome Decoding with Large Weight. In K. G. Paterson, & D. Stebila (Eds.), Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers (pp. 437-466). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11959 LNCS). Springer. https://doi.org/10.1007/978-3-030-38471-5_18

Bricout, Rémi ; Chailloux, André ; Debris-Alazard, Thomas et al. / Ternary Syndrome Decoding with Large Weight. Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers. editor / Kenneth G. Paterson ; Douglas Stebila. Springer, 2020. pp. 437-466 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{701693a9946e4fcba17340ce2c572dc1,

title = "Ternary Syndrome Decoding with Large Weight",

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.",

keywords = "Post-quantum cryptography, Subset sum algorithms, Syndrome decoding problem",

author = "R{\'e}mi Bricout and Andr{\'e} Chailloux and Thomas Debris-Alazard and Matthieu Lequesne",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 26th International Conference on Selected Areas in Cryptography, SAC 2019 ; Conference date: 12-08-2019 Through 16-08-2019",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-38471-5\_18",

language = "English",

isbn = "9783030384708",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "437--466",

editor = "Paterson, \{Kenneth G.\} and Douglas Stebila",

booktitle = "Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers",

}

Bricout, R, Chailloux, A, Debris-Alazard, T & Lequesne, M 2020, Ternary Syndrome Decoding with Large Weight. in KG Paterson & D Stebila (eds), Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11959 LNCS, Springer, pp. 437-466, 26th International Conference on Selected Areas in Cryptography, SAC 2019, Waterloo, Canada, 12/08/19. https://doi.org/10.1007/978-3-030-38471-5_18

Ternary Syndrome Decoding with Large Weight. / Bricout, Rémi; Chailloux, André; Debris-Alazard, Thomas et al.
Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers. ed. / Kenneth G. Paterson; Douglas Stebila. Springer, 2020. p. 437-466 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11959 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Ternary Syndrome Decoding with Large Weight

AU - Bricout, Rémi

AU - Chailloux, André

AU - Debris-Alazard, Thomas

AU - Lequesne, Matthieu

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Post-quantum cryptography

KW - Subset sum algorithms

KW - Syndrome decoding problem

U2 - 10.1007/978-3-030-38471-5_18

DO - 10.1007/978-3-030-38471-5_18

M3 - Conference contribution

AN - SCOPUS:85079524375

SN - 9783030384708

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 437

EP - 466

BT - Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers

A2 - Paterson, Kenneth G.

A2 - Stebila, Douglas

PB - Springer

T2 - 26th International Conference on Selected Areas in Cryptography, SAC 2019

Y2 - 12 August 2019 through 16 August 2019

ER -

Bricout R, Chailloux A, Debris-Alazard T, Lequesne M. Ternary Syndrome Decoding with Large Weight. In Paterson KG, Stebila D, editors, Selected Areas in Cryptography – SAC 2019 - 26th International Conference, Revised Selected Papers. Springer. 2020. p. 437-466. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38471-5_18

Ternary Syndrome Decoding with Large Weight

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this