Has MIMO decoding been proved hard from lattice problems?
Abstract
Multiple-input multiple-output (MIMO) technology is fundamental to modern wireless communication. Physical layer security seeks to protect transmitted information by exploiting properties of the noisy communication channel. Dean and Goldsmith proposed a polynomial time reduction from lattice problems to MIMO decoding by adapting Regev's reduction for learning with errors (LWE). If valid, this reduction would give physical layer security a strong computational foundation based on the hardness of established lattice problems. Subsequent works presented attacks and counterexamples against the resulting construction, casting doubt on its security but leaving the precise validity and limitations of the underlying reduction incompletely understood. We provide a theoretical examination of the revised reduction and identify the structural features of the LWE reduction that fail to carry over to the non-modular MIMO setting, hence showing that its published proof does not establish the claimed hardness of MIMO decoding. Our results distinguish flaws in the hardness proof from direct attacks on particular parameter choices and clarify what would be required of any attempted repair. We do not rule out physical layer security for MIMO systems in general, but show that the claimed lattice hardness guarantee does not follow from the existing reduction.
Related
- Study of Iterative Detection and Decoding for {Mixed Near- and Far-Field} XL-MIMO Systems
- Dual lattice attacks for bounded distance decoding, revisited
- NP-hardness of ideal lattice problems
- Initial-boundary value problems for linear lattice differential equations
- Forbidden subposet problems in the linear lattice
BibTeX
@misc{li2026mimo,
title = {{Has MIMO decoding been proved hard from lattice problems?}},
author = {Yang Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05013},
eprint = {2609.05013},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05013},
}
RIS
TY - UNPB
TI - Has MIMO decoding been proved hard from lattice problems?
AU - Yang Li
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05013
UR - https://arxiv.org/abs/2609.05013
AB - Multiple-input multiple-output (MIMO) technology is fundamental to modern wireless communication. Physical layer security seeks to protect transmitted information by exploiting properties of the noisy communication channel. Dean and Goldsmith proposed a polynomial time reduction from lattice problems to MIMO decoding by adapting Regev's reduction for learning with errors (LWE). If valid, this reduction would give physical layer security a strong computational foundation based on the hardness of established lattice problems. Subsequent works presented attacks and counterexamples against the resulting construction, casting doubt on its security but leaving the precise validity and limitations of the underlying reduction incompletely understood. We provide a theoretical examination of the revised reduction and identify the structural features of the LWE reduction that fail to carry over to the non-modular MIMO setting, hence showing that its published proof does not establish the claimed hardness of MIMO decoding. Our results distinguish flaws in the hardness proof from direct attacks on particular parameter choices and clarify what would be required of any attempted repair. We do not rule out physical layer security for MIMO systems in general, but show that the claimed lattice hardness guarantee does not follow from the existing reduction.
ER -