Faster 2-regular information-set decoding

D.J. Bernstein, T. Lange, C.P. Peters, P. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


Fix positive integers B and w. Let C be a linear code over F 2 of length Bw. The 2-regular-decoding problem is to find a nonzero codeword consisting of w length-B blocks, each of which has Hamming weight 0 or 2. This problem appears in attacks on the FSB (fast syndrome-based) hash function and related proposals. This problem differs from the usual information-set-decoding problems in that (1) the target codeword is required to have a very regular structure and (2) the target weight can be rather high, so that there are many possible codewords of that weight. Augot, Finiasz, and Sendrier, in the paper that introduced FSB, presented a variant of information-set decoding tuned for 2-regular decoding. This paper improves the Augot–Finiasz–Sendrier algorithm in a way that is analogous to Stern’s improvement upon basic information-set decoding. The resulting algorithm achieves an exponential speedup over the previous algorithm.
Original languageEnglish
Title of host publicationCoding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)
EditorsY.M. Chee
Place of PublicationBerlin
ISBN (Print)978-3-642-20901-7
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Faster 2-regular information-set decoding'. Together they form a unique fingerprint.

Cite this