Paper 2020/869

An Algorithmic Reduction Theory for Binary Codes: LLL and more

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


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)
Public-key cryptography
Publication info
Preprint. MINOR revision.
CodesLatticesLLLInformation Set DecodingCryptanalysis
Contact author(s)
thomas debris @ rhul ac uk
ducas @ cwi nl
Wessel van Woerden @ cwi nl
2020-10-15: revised
2020-07-12: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.