Paper 2023/1730

Construction-D lattice from Garcia-Stichtenoth tower code

Abstract

We show an explicit construction of an efficiently decodable family of $n$-dimensional lattices whose minimum distances achieve $\Omega(\sqrt{n} / (\log n)^{\varepsilon+o(1)})$ for $\varepsilon>0$. It improves upon the state-of-the-art construction due to Mook-Peikert (IEEE Trans.\ Inf.\ Theory, no. 68(2), 2022) that provides lattices with minimum distances $\Omega(\sqrt{n/ \log n})$. These lattices are construction-D lattices built from a sequence of BCH codes. We show that replacing BCH codes with subfield subcodes of Garcia-Stichtenoth tower codes leads to a better minimum distance. To argue on decodability of the construction, we adapt soft-decision decoding techniques of Koetter-Vardy (IEEE Trans.\ Inf.\ Theory, no.\ 49(11), 2003) to algebraic-geometric codes.