Bounds and Constructions of Maximum Toroidal Distance Codes
For researchers in lattice-based cryptography, this work provides both theoretical bounds and explicit optimal code constructions for toroidal distances, though the results are incremental in nature.
The paper derives new upper bounds for minimum toroidal distance of codes, including a Plotkin-type bound, a local ball-Plotkin bound, and a Delsarte linear programming bound, and constructs explicit maximum toroidal distance (MTD) codes for dimensions 2, 4, and 8, and a code with minimum distance 3 for dimension 16, improving over the known upper bound of 2√3.
In lattice-based cryptographic schemes, both encoded messages and accumulated decryption noise are represented in a modulo $q$ space. Therefore, it is natural to study toroidal distances and maximum toroidal distance (MTD) codes. In this paper, we derive some upper bounds for minimum toroidal distance of a code, including a Plotkin-type bound, a local ball--Plotkin bound, and a Delsarte linear programming bound. We also exhibit examples showing that these bounds are sharp in some cases. Moreover, we present several code constructions with good minimum distance, some of which are MTD codes. For $\ell=2$, we obtain a family of four-point MTD codes in $\mathbb Z_q^2$. For $\ell=4$, we propose a general code construction and exhibit several explicit instances for specific values of $q$, some of which are proven to be MTD codes. For $\ell=8$, using the $E_8$ lattice, we construct codes $C=2mE_8\cap \mathbb Z_q^8$, where $q=4m$ and show that they are MTD codes. These results give explicit optimal constructions of MTD codes for $\ell=2,4,8$. In the case $\ell=16$, we construct a code with minimum toroidal distance $3$ for $q=4$, while the known upper bound in this case is $2\sqrt{3}$. Our main tools are geometric and linear programming methods.