CS Paper Radar

Has MIMO decoding been proved hard from lattice problems?

Yang Li

cs.CR cs.IT ·submitted 2026-09-04 11:23 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices

cs.CC cs.CR ·2026-11-03 ·Chen Qian
similarity 0.60
Abstract

Can deterministic information loss yield post-quantum pseudorandomness with $TC^0$ evaluation? We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. The proof uses source-independent affine transport: public affine maps sampled independently of the hidden errors transport the Gaussian error law close to uniform on the rounding map's zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $TC^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also prove hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.

0.32

Maurer-Inspired Two-Way Physical-Layer Authentication Against Multi-Antenna Impersonation Attacks

cs.CR ·2026-11-09 ·Pin-Hsun Lin, Linda Senigagliesi, Eduard A. Jorswieck
similarity 0.59
Abstract · 18 pages, 1 figure. Submitted to IEEE ICC 2027

In this work, we investigate Maurer-inspired two-way physical-layer authentication. Alice seeks authentication by Bob in the presence of a multi-antenna impersonator, Trudy. Trudy may replace the challenge to Alice, the response to Bob, or both. To create an information advantage, Bob adds artificial noise (AN) to his challenge, and Alice adds spatial AN while forwarding the received mixture. Bob predicts the response from trusted preparation, whereas Trudy observes only a noisy version of the challenge, and Alice's AN interferes with Trudy's preparation reception. Impersonation thus requires matching Bob's fresh randomness beyond the channel consistency checked by public-pilot one-way authentication. For quasi-static Gaussian multiple-input multiple-output channels with time-division duplex (TDD) reciprocity, we derive missed-detection bounds for attacks that replace the authentication challenge, the response, or both. These bounds assume attack-free initial training and preparation and account for estimation error and AN leakage. With equal antenna numbers at all nodes, we show scenarios where the proposed scheme has lower worst-case missed detection than specified one-way tests with/without AN.

0.36

Adversarial Pilot Injection Against AI-Based CSI Feedback in FDD Massive MIMO Systems

eess.SP ·2026-10-29 ·Jinli Zhai, Yusen Wang, Qimei Cui, Zengbao Zhu, Shengyuan Liang +1 more
similarity 0.57
Abstract · Submitted to IEEE Internet of Things Journal

Artificial intelligence (AI)-based channel state information (CSI) feedback reduces overhead in frequency division duplexing (FDD) massive multiple-input multiple-output (MIMO) systems, yet its reconstructed CSI depends on the integrity of pilot acquisition. This paper identifies and evaluates the attack path of adversarial pilot injection against this feedback. A transmitted disturbance can damage the user-side estimation before encoding; correctly delivered quantized bits can still represent a contaminated channel estimate. We model this path through attacker propagation, linear minimum mean square error estimation, compression, quantization, and decoding under a total transmit-energy constraint. An adversarial perturbation generator (APG) implements the attack using channel statistics without current legitimate CSI or instantaneous attacker-channel observations at deployment. At a Rician attacker-channel factor of 10~dB and a transmit perturbation-to-signal ratio of $-4$~dB, APG produces a normalized mean-square error (NMSE) of 0.84~dB in base-station CSI reconstruction, compared with $-10.31$~dB for Gaussian interference. Estimator-targeted and reconstruction-targeted attacks yield different error orderings, and reconstruction damage also degrades beamforming. As a countermeasure, alternating adversarial training (AAT) adapts the feedback encoder and decoder to contaminated pilots. With condition-matched training and APGs reoptimized for the final receiver, AAT reduces NMSE by 2.40--3.79~dB across six representative channel--power conditions. The results demonstrate the importance of protecting pilot acquisition alongside quantized feedback delivery.

0.28

Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold

cs.IT ·2026-09-16 ·Dimitris Papailiopoulos
theory similarity 0.56
Abstract · 51 pages

We prove that exact block recovery in the square Gaussian binary MIMO model can be achieved in polynomial time at the same first-order SNR threshold as exhaustive maximum-likelihood detection. Specifically, for $y=\sqrt{ρ/N}Hx^\star+w, \; x^\star\in\{\pm1\}^N,$ and independent standard Gaussian $H\in\mathbb R^{N\times N}$ and $w$, rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word and every $ρ\ge2\log N$, using $O(N^3)$ unit-cost exact-real arithmetic operations. The model is a special case of Gaussian random linear estimation, for which AMP state evolution and replica/MMSE formulas rigorously characterize fixed-parameter normalized performance. Those results predict the same $2\log N$ scale, but do not by themselves yield an all-coordinate guarantee in the dimension-dependent regime considered here. To the best of our knowledge, no prior work gives polynomial-time exact block recovery at the ML boundary for this setting; the closest prior square-system theorem, for the box relaxation, has first-order threshold $4\log N$. The proof places the rounded LMMSE estimate at sublinear Hamming distance from the truth, and then establishes, uniformly over every error set the local search can visit, that some wrong bit offers a quantified cost decrease while an objective barrier confines the search path. Conversely, if $0<ρ\le2\log N-\log\log N-s_N$ with $s_N\to\infty$ and $s_N=o(\log N)$, then a one-bit neighbor beats the transmitted word with probability tending to one, so even ML detection fails. Therefore, the statistical and polynomial-time exact-recovery thresholds coincide to first order in the stated arithmetic model.

0.20

Simultaneous Secure Communications and Sensing Privacy with Full Duplex MIMO Radios

eess.SP ·2026-10-14 ·Ioannis Gavras, George C. Alexandropoulos
similarity 0.55
Abstract · 6 pages, 2 figures

This paper proposes a Full Duplex (FD) framework for safeguarding Integrated Sensing and Communications (ISAC) against a passive multi-antenna Eavesdropper (Eve). The adversary is modeled as both a communication and sensing threat, seeking to decode uplink data streams and estimate the surrounding scene. Eve's threat is quantified through two worst-case requirements over a location uncertainty region: a minimum secrecy rate for data confidentiality and a minimum eavesdropping Cramer-Rao Bound (CRB) for sensing privacy. We derive the eavesdropping information measures governing both data interception and scene inference, showcasing that transmitting Artificial Noise (AN) can degrade Eve's capabilities through the inverse interference-plus-noise covariance. Exploiting the underlying structure of the problem, we characterize finite-power local and robust feasibility conditions for target secrecy-privacy pairs. The analysis showcases that AN is fundamentally subspace-limited: increasing power is beneficial only along Eve's communication channel and sensing-derivative directions illuminated by the effective AN subspace. Finally, we formulate an AN power allocation problem that is solved via monotone branch-and-bound, and numerical evaluations quantify the AN power required to guarantee joint secrecy and sensing privacy.

0.14

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.55
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.42

Z-Sigil: A Public-Key Cryptosystem with Chained Selection over a Fiber Bundle of Module-Lattice Keys

cs.CR cs.IT ·2026-09-29 ·Andrea Rondelli
theoryhot direction similarity 0.55
Abstract

Z-Sigil is a public-key cryptosystem in which the plaintext selects successive keys from a fixed module-lattice family. Messages are length-prefixed, zero-padded and divided into 32-byte blocks. Each public vector is a shared public matrix applied to a small secret vector, plus a small error. Key indices label torsion points of a flat Kähler torus; the secret family forms a section of a key bundle over them. A public nonce initializes a hash state that selects each block's key and bit mask. The sender updates the state with the plaintext block; the receiver does so after recovering it. The stream and nonce determine a discrete walk along which decryption reads the secret section. We specify the algorithms, prove correctness under an explicit noise condition and bound decoding failure for messages chosen after the public key. Under stated decisional Module-LWE assumptions, we establish IND-CPA confidentiality for the chain without modelling the state hash as a random oracle. The reduction covers quantum adversaries under quantum hardness assumptions, with classical keys, messages and ciphertexts; no concrete security level is established. With independent uniform selectors, a restricted direct-decryption model quantifies reduced fragment recovery under partial key exposure, without improving full-message recovery probability over an independent-block baseline. Known-plaintext and candidate-message attacks, and parallel candidate-table decryption, delimit this result. Neither a universal sequential lower bound nor authentication or chosen-ciphertext security is established. Replacing an earlier scalar-exposing proposal, we give an augmented-lattice interpretation, integral-transport obstructions and a noise budget for research on curved, nontrivial bundles. A byte-level specification, pseudocode, test vectors and numerical checks support verification.

0.34

Beyond Vector Hiding: Breaking and Mitigating Shared-Direction Weight Obfuscation in TEE-Offloaded Large Language Models

cs.CR ·2026-08-27 ·Menghui Zhang, Aoying Zheng, Guoxiao Liu, Zizhuang Deng, Jiejing Wen +2 more
similarity 0.54
Abstract

Trusted Execution Environment (TEE)-shielded partitioning of Large Language Models (LLMs) accelerates on-device inference by offloading obfuscated linear layers to an untrusted accelerator while retaining only a small correction inside the TEE. However, earlier lightweight obfuscation schemes preserved weight-vector directions and were broken by ArrowMatch. To defend against this attack, ArrowCloak injects scalar multiples of the same hidden direction into all weight vectors, enabling lightweight trusted correction. We show that this reuse leaves a rank-one relation across the complete accelerator-visible matrix. For the released real-valued scheme, we propose SpectralLeak, which estimates and removes the shared component. Across 12 task settings, its surrogates achieve $87.98\%$ mean accuracy versus $89.85\%$ for the victims. In our defense-favorable mod-$Q$ realization of ArrowCloak's published modular security formulation, mod-$Q$ arithmetic suppresses this spectral signal but retains the algebraic rank-one relation modulo $Q$. We therefore propose LatticeLeak, which exploits the resulting hidden lattice. In our BERT-Base and GPT2-Base experiments, it reconstructs every protected fixed-point parameter exactly; across all evaluated architectures, the reconstructed models retain victim-level task accuracy without victim queries, labels, or fine-tuning. These findings identify shared rank-one reuse as the root cause of the leakage exploited by our attacks. Guided by this insight, we design ButterflyCloak, a keyed maximal-rank butterfly mask that replaces the reused direction with distinct mask rows while retaining fast trusted correction...

0.36