Improved Generalized Birthday Attack

Paul Kirchner

Paper 2011/377

Improved Generalized Birthday Attack

Paul Kirchner

Abstract

Let r, B and w be positive integers. Let C be a linear code of length Bw and subspace of Fr . The k-regular-decoding problem is to find 2 a nonzero codeword consisting of w length-B blocks with Hamming weight k. This problem was mainly studied after 2002. Not being able to solve this problem is critical for cryptography as it gives a fast attack against FSB, SWIFFT and learning parity with noise. In this paper, the classical methods are used in the same algorithm and improved.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: Generalized Birthday Attack Linearization Information-Set Decoding Wagner Low memory requirement SWIFFT FSB LPN
Contact author(s): pole kirchner @ gmail com
History: 2011-07-12: received
Short URL: https://ia.cr/2011/377
License: CC BY

BibTeX

@misc{cryptoeprint:2011/377,
      author = {Paul Kirchner},
      title = {Improved Generalized Birthday Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/377},
      year = {2011},
      url = {https://eprint.iacr.org/2011/377}
}