Using these algorithms, we demonstrate ---both with a heuristic analysis and in practice--- a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off.
The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. In constructive cryptography, this algorithmic reduction theory could for example also be helpful for designing trapdoor functions from codes.
Category / Keywords: public-key cryptography / Codes, Lattices, LLL, Information Set Decoding, Cryptanalysis Date: received 10 Jul 2020, last revised 15 Oct 2020 Contact author: thomas debris at rhul ac uk, ducas@cwi nl, Wessel van Woerden@cwi nl Available format(s): PDF | BibTeX Citation Version: 20201015:190129 (All versions of this report) Short URL: ia.cr/2020/869