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 AttackLinearizationInformation-Set DecodingWagnerLow memory requirementSWIFFTFSBLPN
- 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},
note = {\url{https://eprint.iacr.org/2011/377}},
url = {https://eprint.iacr.org/2011/377}
}
