Paper 2011/120

Faster 2-regular information-set decoding

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

Abstract

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, pre- sented 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Information-set decoding2-regular decodingFSBbinary codes
Contact author(s)
tanja @ hyperelliptic org
History
2011-03-10: received
Short URL
https://ia.cr/2011/120
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/120,
      author = {Daniel J.  Bernstein and Tanja Lange and Christiane Peters and Peter Schwabe},
      title = {Faster 2-regular information-set decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2011/120},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/120}},
      url = {https://eprint.iacr.org/2011/120}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.