### An Algorithmic Reduction Theory for Binary Codes: LLL and more

Thomas Debris-Alazard, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CodesLatticesLLLInformation Set DecodingCryptanalysis
Contact author(s)
thomas debris @ rhul ac uk
ducas @ cwi nl
Wessel van Woerden @ cwi nl
History
2020-10-15: revised
See all versions
Short URL
https://ia.cr/2020/869

CC BY

BibTeX

@misc{cryptoeprint:2020/869,
author = {Thomas Debris-Alazard and Léo Ducas and Wessel P. J.  van Woerden},
title = {An Algorithmic Reduction Theory for Binary Codes: LLL and more},
howpublished = {Cryptology ePrint Archive, Paper 2020/869},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/869}},
url = {https://eprint.iacr.org/2020/869}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.