Provable one-wayness or efficient cryptanalysis of the optimization-based one-way-like function in noncoherent massive-MIMO physical-layer security

The physical-layer-security scheme of Katsuki, de Abreu, Ishibashi and Ishikawa (IEEE TIFS 2023) protects noncoherent massive-MIMO differential transmissions by constructing the secret space-time projection matrix $E_1$ through a nonconvex continuous optimization — coding-gain maximization over unit-modulus vectors — started from a pseudo-random initial vector seeded by a channel-derived secret key. Because the optimization has many local minima, the seed-to-matrix map behaves empirically like a one-way function, and even an idealized eavesdropper with perfect channel knowledge, a noise-free prior observation, and asymptotically large SNR cannot recover the matrix when the number of transmit antennas substantially exceeds the eavesdropper's antenna count. The paper itself acknowledges, however, that this property is unproven: the construction is an implementation-level, empirically evaluated, 'one-way-like' primitive, not a one-way function in the cryptographic sense. The open problem is the computational status of this construction: whether inverting it — recovering the seed or initial vector from the projection matrix, or recovering the matrix or the plaintext from an eavesdropper's observations — is hard for probabilistic polynomial-time adversaries, either unconditionally or conditional on an explicitly stated standard average-case hardness assumption, or whether an efficient inversion or decryption attack exists under the paper's own idealized adversary model. Neither a hardness result nor an efficient inversion or decryption attack for this construction is known, so the problem remains open.

Background

Physical-layer security (PLS) protects wireless transmissions by exploiting properties of the physical channel rather than upper-layer cryptographic algorithms. Massive multiple-input multiple-output (MIMO) systems — arrays with tens to hundreds of antennas — are attractive for PLS because the high dimensionality of the channel makes eavesdropping difficult. A persistent obstacle is that most PLS designs assume the legitimate pair knows the channel precisely (perfect channel state information, CSI), which requires pilot transmissions that are themselves observable by an eavesdropper and vulnerable to pilot-contamination attacks, in which an attacker transmits during the training phase to corrupt the channel estimate. This motivates noncoherent schemes based on differential space-time modulation, which need no channel estimation: information is encoded in the relationship between successively transmitted space-time blocks. In nonsquare differential space-time coding (N-DSTC), an $M \times T$ projection matrix, with $T < M$ transmit antennas and time slots, compresses the space-time signal while preserving transmission rate in massive-MIMO settings.

Katsuki, de Abreu, Ishibashi and Ishikawa (IEEE TIFS 2023) proposed an N-DSTC scheme with embedded physical-layer security in which the projection matrix is produced by the following pipeline. A secret seed $z$ — in a full physical-layer implementation extracted from the reciprocal Alice–Bob wireless channel, whose randomness is the source of secrecy — deterministically generates a pseudo-random initial vector $\mathbf{e}_1^{(0)} \in \mathbb{C}^{M}$; an iterative continuous optimizer (the paper adopts SLSQP, sequential least-squares quadratic programming, a standard nonlinear optimization method) then solves

$\min_{\mathbf{e}_1 \in \mathbb{C}^{M}} \; \sum_{n=1}^{M/2} \left| \mathbf{e}_1^{\mathrm{H}} \mathbf{M}^n \mathbf{e}_1 \right| \quad \text{subject to} \quad |e_m|^2 = 1, \; m = 1, \dots, M,$

where $\mathbf{M}$ is the $M \times M$ cyclic-shift permutation matrix (its powers rotate the entries of a vector), so the objective sums the magnitudes of the cyclic autocorrelations of $\mathbf{e}_1$; the converged vector is then sparsified and expanded by column-wise cyclic rotations into the projection/encryption matrix $E_1$ that differentially encodes the transmitted blocks. Because this problem is nonconvex over a constraint manifold with many local minima, the converged solution depends on both the solver and the initial value, so the map from the seed to $E_1$ behaves — empirically — like a one-way function, the basic primitive of modern cryptography: a function that is easy to compute but computationally hard to invert. The paper demonstrates that even an idealized eavesdropper Eve, granted perfect knowledge of her own channel matrix $\mathbf{H}_{\mathrm{Eve}}$, a noise-free copy of a known transmitted block, and asymptotically large signal-to-noise ratio (SNR), cannot recover $E_1$ or decrypt traffic whenever the number of transmit antennas $M$ is substantially larger than Eve's antenna count $N_{\mathrm{Eve}}$: the information leakage, measured as $1 - 2 \times \mathrm{BER}_{\mathrm{Eve}}$ where $\mathrm{BER}_{\mathrm{Eve}}$ is Eve's bit error rate (leakage 0 corresponds to random guessing, leakage 1 to perfect decoding), reaches zero for the evaluated configurations with $M$ up to 128 and $N_{\mathrm{Eve}} \le 16$.

What remains unresolved is the hardness status of this construction. In cryptography, a one-way function must be hard to invert for all probabilistic polynomial-time adversaries on average over the input distribution; whether one-way functions exist at all is a famous open problem — their existence would imply $\mathrm{P} \ne \mathrm{NP}$, and Liu and Pass (2020) proved it equivalent to the mild average-case hardness of time-bounded Kolmogorov complexity (roughly, the length of the shortest program that outputs a given string within a given time budget). The paper is explicit about this gap: footnote 2 states that no one has yet answered whether one-way functions exist in the cryptographic sense, and the construction is accordingly described as 'one-way-like' — an implementation-level primitive whose inversion hardness is evaluated only empirically. A neighboring line of work shows what a provable counterpart looks like: Dean and Goldsmith (2017) and Liu et al. (AsiaCCS 2024) build physical-layer cryptosystems from massive MIMO whose eavesdropper-decoding problems reduce to lattice problems (finding short vectors in high-dimensional point lattices, conjectured hard for classical and quantum computers), yielding conditional — not unconditional — security statements. No such reduction, and no efficient inversion attack, is known for the nonconvex-optimization-based construction above.

Problem Statement

Determine the computational one-wayness of the optimization-based secret-projection construction embedded in the noncoherent massive-MIMO physical-layer-security scheme of Katsuki et al. (IEEE TIFS, 2023). In that scheme, a secret seed $z$ (in a full physical-layer implementation, extracted from the reciprocal Alice–Bob channel) deterministically generates a pseudo-random initial vector $\mathbf{e}_1^{(0)} \in \mathbb{C}^{M}$; an iterative continuous optimizer (SLSQP, with solver parameters possibly also derived from $z$) solves

$\min_{\mathbf{e}_1 \in \mathbb{C}^{M}} \; \sum_{n=1}^{M/2} \left| \mathbf{e}_1^{\mathrm{H}} \mathbf{M}^n \mathbf{e}_1 \right| \quad \text{subject to} \quad |e_m|^2 = 1, \; m = 1, \dots, M,$

where $\mathbf{M}$ is the $M \times M$ cyclic-shift permutation matrix; the converged vector is sparsified and expanded by column-wise cyclic rotations into the projection/encryption matrix $E_1$ used to differentially encode the transmitted blocks. The question, left explicitly unresolved by the source (which describes the map as only 'one-way-like'), is whether the construction is computationally one-way in a precisely specified model — the seed and channel input distributions, the exact construction pipeline, and adversary access stated per target: the inversion adversary is given $E_1$ together with the public description of the pipeline, while the decryption adversary has exactly the observations of the scheme's eavesdropper model.

A hardness result states that no probabilistic polynomial-time adversary can invert the construction with non-negligible probability, that is, that no such adversary, given $E_1$, can output any seed or initial vector that the fixed construction pipeline maps to $E_1$ (a preimage, not necessarily the particular input used), nor recover $E_1$ or the plaintext from the eavesdropper's own observations; it may be conditional on an explicitly stated standard average-case hardness assumption (an established assumption independent of this construction, not the hardness of inverting the construction itself).

A refutation is a polynomial-time (in $M$) attack that, under the paper's own idealized eavesdropper conditions (perfect knowledge of $\mathbf{H}_{\mathrm{Eve}}$, a noise-free prior observation, asymptotically high SNR), recovers $E_1$ or decrypts traffic with error probability bounded away from random guessing in the regime where the construction claims zero leakage ($M$ substantially larger than $N_{\mathrm{Eve}}$).

For the source's asymptotic claim that security improves with the number of transmit antennas, a single finite-instance break does not suffice: the attack must remain efficient as $M$ grows at a fixed or growing $M/N_{\mathrm{Eve}}$ ratio. Absent either resolution, the primitive's security remains an empirical, implementation-level property, which is exactly the status the source leaves it in.

References

1. Yuma Katsuki, Giuseppe Thadeu Freitas de Abreu, Koji Ishibashi, Naoki Ishikawa, “Noncoherent Massive MIMO With Embedded One-Way Function Physical Layer Security,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 3158–3170, 2023. DOI: 10.1109/TIFS.2023.3277255 (arXiv:2202.11893). https://arxiv.org/abs/2202.11893
2. Thomas R. Dean, Andrea J. Goldsmith, “Physical-Layer Cryptography Through Massive MIMO,” IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 5419–5436, 2017. DOI: 10.1109/TIT.2017.2715187. https://doi.org/10.1109/TIT.2017.2715187
3. Senlin Liu, Tong Gao, Yijian Liu, Xianhui Lu, “Physical-Layer Public Key Encryption Through Massive MIMO,” in Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (AsiaCCS 2024), 2024, pp. 353–365. DOI: 10.1145/3634737.3656284. https://doi.org/10.1145/3634737.3656284
4. Yanyi Liu, Rafael Pass, “On One-way Functions and Kolmogorov Complexity,” 2020. arXiv:2009.11514. https://arxiv.org/abs/2009.11514
5. Yuma Katsuki, Naoki Ishikawa, “Optimal but Low-Complexity Optimization Method for Nonsquare Differential Massive MIMO,” in IEEE 94th Vehicular Technology Conference (VTC2021-Fall), 2021. DOI: 10.1109/VTC2021-FALL52928.2021.9625337 (arXiv:2305.16679). https://arxiv.org/abs/2305.16679
6. Ali Khandan Boroujeni, Giuseppe Thadeu Freitas de Abreu, Stefan Köpsell, Ghazal Bagheri, Kuranage Roche Rayan Ranasinghe, Rafael F. Schaefer, “Frequency Hopping Waveform Design for Secure Integrated Sensing and Communications,” IEEE Transactions on Information Forensics and Security, vol. 21, pp. 3719–3734, 2026. DOI: 10.1109/TIFS.2026.3680069 (arXiv:2504.10052). https://arxiv.org/abs/2504.10052