Faster 2-Regular Information-Set Decoding

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

Not written here

  • Author: Bernstein, Daniel J.

    University of Illinois at Chicago, Department of Computer Science

  • Author: Lange, Tanja

    Technische Universiteit Eindhoven, Department of Mathematics and Computer Science

  • Author: Peters, Christiane

    Unknown

  • Author: Schwabe, Peter

    Academia Sinica, Institute of Information Science

View graph of relations

Fix positive integers B and w. Let C be a linear code over F2 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 syndromebased) 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.
Keyword: 2-regular decoding,Binary Codes,FSB,Information-set decoding
Original languageEnglish
TitleLecture Notes in Computer Science
Volume6639
PublisherSpringer Publishing Company
Publication date2011
Pages81-98
StatePublished

Workshop

Workshop3rd International Workshop on Coding and Cryptology
Number3
CountryChina
CityQingdao
Period30/05/1103/06/11
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 6461991