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
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2020-07-12: received
- See all versions
- Short URL
- https://ia.cr/2020/869
- License
-
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}
}
