Has MIMO decoding been proved hard from lattice problems?
Researchers show the published lattice-hardness proof for MIMO decoding fails, as Regev's LWE reduction structure does not carry over to non-modular MIMO.
The paper re-examines Dean and Goldsmith's proposed polynomial-time reduction from lattice problems to MIMO decoding, which adapted Regev's reduction for learning with errors (LWE). Prior works had presented attacks and counterexamples against the construction, leaving the reduction's precise validity unclear. The authors identify which structural features of the LWE reduction fail to transfer to the non-modular MIMO setting, showing the published proof does not establish the claimed hardness of MIMO decoding. They distinguish flaws in the hardness proof from direct attacks on specific parameter choices and do not rule out physical layer security for MIMO systems in general.
- Dean-Goldsmith reduction from lattice problems to MIMO decoding adapted Regev's LWE reduction.
- Structural LWE features fail to carry over to the non-modular MIMO setting.
- Published proof does not establish the claimed hardness of MIMO decoding.
- Results separate proof flaws from attacks on particular parameter choices.
- Physical layer security for MIMO is not ruled out in general.
Full article194 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.05013