Faster 2-Regular Information-Set Decoding

Daniel J. Bernstein; Tanja Lange; Christiane Peters; Peter Schwabe

Faster 2-Regular Information-Set Decoding

Daniel J. Bernstein, Tanja Lange, Christiane Peters, Peter Schwabe

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

Abstract

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 language	English
Title of host publication	Lecture Notes in Computer Science
Volume	6639
Publisher	Springer Publishing Company
Publication date	2011
Pages	81-98
Publication status	Published - 2011
Externally published	Yes
Event	3rd International Workshop on Coding and Cryptology - Qingdao, China Duration: 30 May 2011 → 3 Jun 2011 Conference number: 3

Workshop

Workshop	3rd International Workshop on Coding and Cryptology
Number	3
Country/Territory	China
City	Qingdao
Period	30/05/2011 → 03/06/2011

OpenUrl availability

Full text

Cite this

@inproceedings{4ba9bd7de21e43c99d046228c83a8760,

title = "Faster 2-Regular Information-Set Decoding",

abstract = "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{\textquoteright}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",

author = "Bernstein, {Daniel J.} and Tanja Lange and Christiane Peters and Peter Schwabe",

year = "2011",

language = "English",

volume = "6639",

pages = "81--98",

booktitle = "Lecture Notes in Computer Science",

publisher = "Springer Publishing Company",

address = "United States",

note = "3rd International Workshop on Coding and Cryptology, IWCC 2011 ; Conference date: 30-05-2011 Through 03-06-2011",

}

TY - GEN

T1 - Faster 2-Regular Information-Set Decoding

AU - Bernstein, Daniel J.

AU - Lange, Tanja

AU - Peters, Christiane

AU - Schwabe, Peter

N1 - Conference code: 3

PY - 2011

Y1 - 2011

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

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

M3 - Article in proceedings

VL - 6639

SP - 81

EP - 98

BT - Lecture Notes in Computer Science

PB - Springer Publishing Company

T2 - 3rd International Workshop on Coding and Cryptology

Y2 - 30 May 2011 through 3 June 2011

ER -

Faster 2-Regular Information-Set Decoding

Abstract

Workshop

OpenUrl availability

Fingerprint

Cite this