Skip to content

Beyond Explicit Generators: Distribution-Free Linear-Decomposition Attacks on Public-Key Encryption

Aug 2026 · arXiv.org · Vol abs/2608.20798 · 0 citations · 21 references
Computer Science

TL;DR

A setting in which the adversary uses only the public sampling-and-evaluation oracle available to honest participants, the induced distribution is arbitrary, and the goal is to attack future ciphertexts rather than recover the full algebraic span is studied, yielding a generic impossibility theorem.

Abstract

Linear-decomposition attacks can break public-key schemes without recovering the secret algebraic action: when a target public state lies in a known linear span, its decomposition coefficients transfer through the unknown action to reveal the shared value. We study a setting in which the adversary uses only the public sampling-and-evaluation oracle available to honest participants, the induced distribution is arbitrary, and the goal is to attack future ciphertexts rather than recover the full algebraic span. We model public paired samples under a fixed secret linear transport and define the sampled-orbit dimension as the effective dimension of the encryption distribution. We prove distribution-free one-shot recovery, a high-probability certificate for the future-ciphertext coverage of a sampled span, and the optimal sampled-span complexity $m^\star_{\mathrm{span}}(r,\varepsilon,\delta) =\Theta((r+\log(1/\delta))/\varepsilon)$. These results yield a generic impossibility theorem: publicly samplable linear key transport with polynomial sampled-orbit dimension is incompatible with IND--CPA security when the transported value determines the decryption payload. We apply the framework to the 2024 probabilistic PKE from twisted--skew group rings. Its underlying Computational Twisted--Skew Problem admits a sampler-only linear attack using independently generated public protocol samples, yielding plaintext recovery and constant IND--CPA advantage. Experiments verify the linear transport and end-to-end recovery, and show that high future-ciphertext coverage may precede recovery of the full algebraic span.

View source

Similar papers

Preprint Sep 2026

Stabilizer-Public-Key Authentication: Long Stabilizer Public Keys Resist Finite-Copy Forgery Attacks

We propose an information-theoretic authentication protocol based on a finite supply of long quadratic-stabilizer public-key states over an odd-prime field, where the effective key length after one signature exposure is the residual dimension $r=n-\ell$. A computationally unbounded adversary observes one valid classica...

Masahito Hayashi, Jing-Tian Zhao, Bai-Chu Yu · 0 citations
Preprint Oct 2026

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

A new modification of the ramp secret sharing scheme, called compact sharing, is introduced, and the MPC protocol is tailored to accommodate this modification, which provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree.

Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik et al. · 0 citations
Preprint Oct 2026

Quantum-Aware Key Rank for Side-Channel Attacks evaluation

Side-channel attacks on block ciphers rarely recover the key outright: they leave a residual key space ordered by subkey posteriors, and evaluation laboratories report the key rank of the true key against thresholds near 2^48 and 2^60. No evaluation framework models an adversary who collects traces classically and fini...

Y. Kotukh · 0 citations
Preprint Oct 2026

Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity

We study a protocol-level reaction leakage in CKKS deployments where public coefficient-to-slot (C2S) evaluation keys are combined with a client's 1-bit validity response. Under this deployment surface, a malicious evaluator can recover a ternary secret key using asymptotically optimal $O(H)$ reaction queries, where $H...

S. Bian, Hyeong-Soon Choe, Jiseung Kim et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.