Cryptology ePrint Archive: Report 2020/869

An Algorithmic Reduction Theory for Binary Codes: LLL and more

Thomas Debris-Alazard and Léo Ducas and Wessel P.J. van Woerden

Abstract: In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.

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