期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 68, 期 5, 页码 3426-3444出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2022.3143620
关键词
Codes; Lattices; Cryptography; Decoding; Binary codes; Measurement; Heuristic algorithms; Codes; lattices; LLL; information set decoding; cryptanalysis
资金
- EPSRC [EP/S02087X/1]
- French Agence Nationale de la Recherche through ANR JCJC COLA [ANR-21-CE39-0011]
- European Union [780701]
- ERC [947821, 740972]
- Agence Nationale de la Recherche (ANR) [ANR-21-CE39-0011] Funding Source: Agence Nationale de la Recherche (ANR)
- European Research Council (ERC) [740972, 947821] Funding Source: European Research Council (ERC)
This article proposes an adaptation of the algorithmic reduction theory of lattices to binary codes, including the LLL algorithm and adaptations of associated algorithms. It demonstrates a small polynomial speed-up over existing algorithms for random binary codes, without relying on time-memory trade-offs.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据