CS Paper Radar

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

Ziyan Chen, Ding-Xuan Zhou

cs.CR ·submitted 2026-08-21 07:16 UTC · v1
theory

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.

Comment
15 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Bilinear Compressive Security with Finitely Many Samples

cs.CR cs.ITeess.SP ·2026-10-14 ·Axel Flinth, Semira Einsele, Matilda Kylberg, Hubert Orlicki, Gerhard Wunder
similarity 0.63
Abstract

Bilinear Compressive Security (BCS) is a lightweight encryption scheme that combines compressed sensing with a fresh random convolution filter to improve resistance against key-recovery attacks under key reuse. Previous work derived information-theoretic guarantees for BCS by relating key identifiability to phase retrieval under the assumption that an adversary has access to the full ciphertext distribution induced by the random filter. In practice, however, an adversary only observes finitely many encryptions, leaving the security of BCS in the finite-sample regime largely unexplored. In this paper, we study key recovery from only finitely many observations. We first develop a covariance-based attack that estimates the linear measurements from repeated encryptions of the same plaintext and subsequently recovers the secret measurement matrix. We analyze the estimation procedure and derive finite-sample guarantees together with corresponding sample-complexity bounds. We further investigate the complete attack experimentally and compare its observed recovery behavior with the previously established information-theoretic identifiability results. Our experiments show two qualitatively different recovery regimes on the structure of the measurement matrix. For dense matrices, including Gaussian matrices, the number of measurements required for successful recovery appears to grow linearly with the signal dimension. This differs from the worst-case behavior suggested by information theory. In contrast, for matrices with sparse rows, we observe a quadratic growth consistent with the theoretical bound. These results suggest that the sparsity structure of the measurement matrix plays an important role in the security of BCS and should be taken into account when selecting parameters and designing practical instances of the scheme.

0.22

A Complexity-Theoretic Approach to Proofs of Space

cs.CR cs.CC ·2026-08-10 ·Marshall Ball, Jiaxin Guan
published similarity 0.60
Abstract

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

0.22

Improved Degree Tables for Secure Distributed Matrix Multiplication

cs.IT math.CO ·2026-09-06 ·John Byrne, Rafael G. L. D'Oliveira, Michael Tait
theory similarity 0.59
Abstract

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any $T$ colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{DOG}_{r,s}$. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{COVER}_r$. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

0.14

Hiding Directions, Leaking Structure: Breaking ArrowCloak through Low-Rank Structure

cs.CR ·2026-08-21 ·Beijie Liu, Junyi Ouyang, Haoxuan Xu, Vincent Quentin Ulitzsch, Potung Yu +2 more
similarity 0.58
Abstract · 17 pages, 3 figures

TEE-shielded inference keeps sensitive state in a trusted execution environment (TEE) while offloading linear algebra to an untrusted accelerator. Wang et al., in Game of Arrows (USENIX Security 2025), showed that five widely adopted lightweight defenses preserve vector directions and introduced ArrowMatch to exploit this leakage. They then proposed ArrowCloak, which adds a different multiple of one shared mask direction to each vector and bases its weight-recovery hardness argument on Learning with Errors (LWE). ArrowCloak successfully reduces ArrowMatch to near-black-box levels. In this paper, we revisit ArrowCloak from cryptographic and structural perspectives. Its LWE formulation does not by itself establish standard LWE hardness: the reduction direction, quantized arithmetic, and joint instance distribution do not meet the required conditions. Reusing one mask direction leaves a recoverable rank-one component across the released matrix. We exploit this structure with our proposed attack, an end-to-end, query-free recovery attack. Given a public checkpoint and the obfuscated weights, the attack removes the masking subspace, recovers the hidden one-to-one correspondence, and reconstructs protected weights without transformation secrets, victim queries, or fine-tuning data. Across six model-task pairs spanning classification, segmentation, and diffusion, the attack recovers 99.92%-100% of hidden vector correspondences. Reconstructed classification models achieve 94.39%-99.54% victim agreement and differ by at most 1.59 percentage points in accuracy; the recovered segmentation model achieves 98.35% output agreement. These findings suggest that lightweight protection should address both per-vector geometry and joint structure across released weights.

0.53

No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

cs.DS cs.LG ·2026-10-18 ·Edith Cohen, Uri Stemmer
similarity 0.58
Abstract

Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension $k$. For adaptive black-box queries, known privacy-based defenses guarantee $\widetildeΩ(k^2)$ and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $Ω(α)$ relative error. This fraction can be taken arbitrarily close to one half. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.

0.25

Low-Rank Masking for Single-Server Matrix Multiplication

cs.IT cs.CR ·2026-09-16 ·Alejandro Cohen, Rafael G. L. D'Oliveira, Alex Sprintson
theory similarity 0.58
Abstract

We study the statistical privacy of outsourcing matrix multiplication over a finite field ${\mathbb F_q}$ to a single server using additive masks of rank at most $r$. For independent uniform $n\times n$ inputs, we show that uniform \emph{rank-ball masks} and products of independent uniform factors give maximal-correlation secrecy of at most $q^{-r}$ against the complete server view, with $O(n^2r)$ field operations for encoding and decoding. This secrecy captures how effectively the server is prevented from estimating functions of the inputs. We prove an asymptotically matching lower bound of this secrecy measure for $r=o(n)$, showing that both sampling methods are asymptotically optimal among input-independent additive masks of rank at most $r$, even when secret invertible transformations are allowed. We also characterize the posterior distribution for uniform rank-ball masks under arbitrary joint input distributions and prove approximate individual security for rows and columns under independent uniform inputs. Finally, we show that every input-independent additive mask of rank at most $r=o(n)$ requires $δ\to1$ in entry-level $(\varepsilon,δ)$-differential privacy for fixed field size $q$ and bounded $\varepsilon$.

0.10

Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography

cs.CC ·2026-11-03 ·Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith
similarity 0.57
Abstract

We study the possibility of basing fine-grained cryptography on the hardness of fundamental problems in linear algebra. Our main technical contribution is a hardness self-amplification method based on random low-rank updates: we show how to turn an algorithm that solves an inverse-polynomial fraction of random linear systems into a solver which succeeds for every right-hand side of almost every matrix. Our reduction increases the runtime only linearly in the inverse of the original success probability. In particular, this yields fine-grained one-way functions from the almost worst-case hardness of linear systems over large enough fields. Using the same approach, we also obtain tighter worst-case to average-case reductions for matrix multiplication and online matrix-vector multiplication, as well as variants of our reductions that recover exact solutions from approximate algorithms, whose expected coordinate agreement is only $1/q+\varepsilon$, with inverse-quadratic dependence on $\varepsilon$ up to logarithmic factors, over every finite field. Finally, we also use it to connect the existence of fine-grained key agreement to the problem of computing the rank of a matrix: over a suitable sequence of growing characteristic-two fields, the almost-everywhere average-case hardness of rank computation (for any of a large class of distributions) implies infinitely-often fine-grained key agreement.

0.18

Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity

cs.CR ·2026-10-15 ·Song Bian, Hyeongmin Choe, Jiseung Kim, Changmin Lee
top venuetheory similarity 0.57
Abstract · Accepted to the 2027 IEEE Symposium on Security and Privacy

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$ is the entropy of the secret key. The attack does not break RLWE or CKKS IND-CPA security. Instead, it exploits the interaction between client-side validity reactions and public homomorphic linear transformations. A shift of a public encryption key yields a ciphertext whose plaintext is a function of the secret key; the public ${\sf C2S}$ layer then repacks this information to construct a ciphertext whose validity depends strictly on whether a targeted secret coefficient matches a guessed value. Furthermore, each submitted query is independently randomized with a fresh encryption of zero, so that each resulting malicious ciphertext appears entirely distinct, thereby allowing the attack to simply evade trivial detection mechanisms on the client side. We implemented the full end-to-end attack in Lattigo v6.2.0 and recovered the full secret key across four parameter sets drawn from standard CKKS presets. For uniform ternary secrets, the attack uses $O(N)$ queries and is within a factor $2/\log_2 3 < 2$ of the oracle-only entropy lower bound. For sparse ternary secrets, a tailored variant further reduces the number of queries in practice. Our results show that observable validity reactions form a practical key-recovery channel in CKKS deployments exposing this surface, even when the underlying cryptographic assumptions remain intact.

0.36