Improved Generalized Birthday Attack

Paul Kirchner

Paper 2011/377 Original: eprint.iacr.org/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
Publication info: Preprint.
History: 2011-07-12: last updated; 2011-07-12: published
Short URL: https://ia.cr/2011/377
License: https://creativecommons.org/licenses/by/4.0/

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