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

• URL: http://arxiv.org/abs/2608.20798v1
• Date: Fri, 21 Aug 2026 07:16:55 GMT
• Title: Beyond Explicit Generators: Distribution-Free Linear-Decomposition Attacks on Public-Key Encryption
• Abstract summary: We study a setting in which adversary uses only public sampling-and-text oracles available to honest participants.<n>We model public paired samples under a fixed secret linear transport and define the sampled-orbit as the effective dimension of the encryption distribution.<n>Experiments verify the linear transport and end-to-end recovery, and show that high future-ciphertext coverage may precede recovery of the full algebra span.
• Score: 13.325673179579818
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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,δ) =Θ((r+\log(1/δ))/\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.

Related papers

• Verifiable Random Sampling [0.6085546687631446]
  Verifiable random functions (VRF) underpin a wide range of applications that require publicly verifiable evaluations of a pseudorandom function on a given input.<n>We introduce the formal notion of verifiable random sampling (VRS)<n>VRS supports multiparty protocols in which the verifier's final output is a sample that is statistically close to a specified target distribution.
  arXiv  Detail & Related papers  (2026-07-29T10:27:08Z)
• C$^{2}$R: Cross-sample Consistency Regularization Mitigates Feature Splitting and Absorption in Sparse Autoencoders [56.67585330425431]
  Sparse Autoencoders (SAEs) are widely used to interpret large language models by decomposing activations into sparse, human-understandable features.<n>These issues stem from inconsistent latent assignment across samples.<n>We introduce C$2$R, which penalizes the co-activation of directionally similar latents.
  arXiv  Detail & Related papers  (2026-06-29T17:45:31Z)
• PAC-Bayesian Certificates for Quadratic Closed-Loop Control [0.0]
  PAC-Bayesian bounds provide finite-sample guarantees for data-dependent predictors.<n>Applying them to learning-based control is difficult because the natural objective is a quadratic trajectory cost.<n>We provide a set of PAC-Bayes-Chernoff certificates for posterior distributions over feasible closed-loop responses.
  arXiv  Detail & Related papers  (2026-06-26T17:24:21Z)
• Hacking Generative Perplexity: Why Unconditional Text Evaluation Needs Distributional Metrics [49.443264461057645]
  Diffusion and continuous flow-based language models have emerged as the leading non-autoregressive alternatives to language modeling.<n>Progress in both paradigms is overwhelmingly tracked by generative perplexity (gen-PPL): the per-token negative log-likelihood of samples under a frozen autoregressive (AR) scorer.<n>We argue that this metric is unsound. By construction, gen-PPL measures only predictability under the scoring AR, not grammaticality or semantic coherence.
  arXiv  Detail & Related papers  (2026-06-07T02:35:56Z)
• Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields [0.0]
  The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol.<n>Recent interest has shifted toward instantiations over extension fields $mathbbF_pr$.<n>This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $mathbbF_pr$.
  arXiv  Detail & Related papers  (2026-04-06T16:35:32Z)
• Finite-sample guarantees for data-driven forward-backward operator methods [1.9336815376402718]
  We consider the problem of finding a zero of the sum of two operators, where one is either unavailable in closed form or computationally expensive to evaluate.<n>Under the lens of algorithmic stability, we derive probabilistic bounds on the distance between a true zero and the FB output.<n>We then specialize our results to a popular FB Nash seeking algorithm and validate our theoretical bounds on a control problem for smart grids.
  arXiv  Detail & Related papers  (2025-12-22T09:07:09Z)
• Breaking Privacy in Federated Clustering: Perfect Input Reconstruction via Temporal Correlations [15.144981031301512]
  Federated clustering allows multiple parties to discover patterns in distributed data without sharing raw samples.<n>Many protocols disclose intermediate centroids during training to reduce overhead.<n>We show that centroid disclosure in federated clustering significantly compromises privacy.
  arXiv  Detail & Related papers  (2025-11-10T13:06:16Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• Robust computation of optimal transport by $\eta$-potential regularization [79.24513412588745]
  Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
  arXiv  Detail & Related papers  (2022-12-26T18:37:28Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• CC-Cert: A Probabilistic Approach to Certify General Robustness of Neural Networks [58.29502185344086]
  In safety-critical machine learning applications, it is crucial to defend models against adversarial attacks. It is important to provide provable guarantees for deep learning models against semantically meaningful input transformations. We propose a new universal probabilistic certification approach based on Chernoff-Cramer bounds.
  arXiv  Detail & Related papers  (2021-09-22T12:46:04Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.