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

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

Dingxuan Zhou

University of Sydney Sydney, New South Wales, Australia

University of Sydney Sydney, New South Wales, Australia

arXiv:2608.20798v1 [cs.CR] 21 Aug 2026

Abstract Linear-decomposition attacks show that recovering a secret algebraic action is often unnecessary in breaking public key scheme: once a target public state lies in a known linear span, the same decomposition coefficients can be transferred through the unknown action to recover the shared value. Prior work has also observed that random public samples may replace an explicitly constructed basis under suitable sampling conditions. We study a different regime motivated by public-key encryption, where the adversary uses only the public sampling-and-evaluation oracle available to an honest participant, the induced distribution may be arbitrary, and the objective is to attack independently generated future ciphertexts without recovering the entire algebraic span. We formalize this setting as public paired samples with a fixed secret linear transport and introduce the sampled-orbit dimension as the effective dimension of the encryption distribution. We give a distribution-free one-shot recovery guarantee, derive a highprobability certificate for the fraction of future ciphertexts covered by a fixed sampled span, and establish the optimal sampled-span complexity 𝑚★span (𝑟, 𝜀, 𝛿) = Θ((𝑟 + log(1/𝛿))/𝜀). We then translate these results into a generic impossibility theorem showing that publicly samplable linear key transport with polynomial sampled-orbit dimension is incompatible with IND–CPA security whenever the transported value determines the decryption payload. Finally, we instantiate the framework against the 2024 probabilistic PKE from twisted–skew group rings. We show that its underlying Computational Twisted–Skew Problem admits a sampler-only linear attack using only independently generated public protocol samples, which in turn yields plaintext recovery and constant IND– CPA advantage. Our experiments validate the exact linear-transport structure, demonstrate end-to-end plaintext recovery, and illustrate that high future-ciphertext coverage may arise well before recovery of the full algebraic span.

secret action 𝐴 give a public value without showing 𝐴 𝑤 = 𝐴𝑣. A fresh sender samples a secret action 𝐵 𝜌 and forms 𝑋 𝜌 = 𝐵 𝜌 𝑣. When the two actions are compatible, for example when 𝐴𝐵 𝜌 = 𝐵 𝜌 𝐴, both sides can obtain the same transported value 𝑌𝜌 = 𝐵 𝜌 𝑤 = 𝐴(𝐵 𝜌 𝑣) = 𝐴𝑋 𝜌 . Thus, from the attacker’s perspective, the cryptographic computation exposes a simple but consequential structure: 𝑌𝜌 = 𝐴𝑋 𝜌 , where 𝐴 is a fixed secret linear map and 𝜌 is fresh public randomness. Commutativity is only one mechanism producing this identity; the results of this paper require only the fixed key transport. Linear decomposition cryptanalysis. A central lesson of algebraic cryptanalysis is that recovering the secret action 𝐴 itself may be unnecessary. Myasnikov and Roman’kov introduced the linear decomposition attack (LDA), showing that shared cryptographic values can often be recovered in polynomial time from linear relations using public elements [12]. Ben-Zvi, Kalka, and Tsaban subsequently developed the broader algebraic-span viewpoint, obtaining polynomial-time cryptanalysis of several noncommutative algebraic protocols [3]. Related work also developed generic lineardecomposition attacks for two-sided multiplication protocols [16]. The algebraic principle underlying these attacks is powerful. 𝑚 with Suppose an adversary observes (𝑋𝑖 , 𝑌𝑖 )𝑖=1 𝑌𝑖 = 𝐴𝑋𝑖 ,

𝑖 = 1, . . . , 𝑚.

If a target published by a sender satisfies 𝑚 ∑︁ 𝑋★ = 𝛼 𝑖 𝑋𝑖 , 𝑖=1

Keywords linear decomposition attack, public-key encryption, IND-CPA, twisted–skew group rings

1

Introduction

Public-key encryption (PKE) is a foundational cryptographic primitive: anyone holding the public key can generate a ciphertext, while only the holder of the secret key should be able to recover the encrypted message. A recurring design pattern in algebraic public-key cryptography realizes this functionality through secret algebraic actions on public objects. In a typical commuting-action construction, such as the Ko–Lee paradigm [9], a public base point 𝑣 and a

then linearity immediately transfers the same coefficients through the unknown secret map to solve the shared key: 𝑚 ∑︁ 𝑌 ★ = 𝐴𝑋 ★ = 𝛼𝑖 𝑌𝑖 . 𝑖=1

Thus, once the target lies in a known public span, the secret shared key can be recovered without solving 𝐴. This coefficient-transfer principle is a classical result.

Chen and Zhou

From random spanning to future-ciphertext coverage. The use of random public samples in linear-decomposition cryptanalysis is also not new. In particular, Roman’kov observed that randomly sampled vectors can replace an explicitly constructed basis under suitable sampling conditions, and used this idea in the cryptanalysis of the Modified Matrix Modular Cryptosystem [17]. It leaves open, however, a different question. Honest encryption does not generally provide a uniform sampler over an entire algebraic span. Instead, it induces some possibly highly non-uniform distribution 𝜇 over public states 𝑋 𝜌 . Moreover, an attacker need not recover the entire span in order to break a future encryption, but only the span learned from public samples to contain an independently generated future target 𝑋 ★ ∼ 𝜇. The relevant quantity is therefore not whether the samples generate the whole space, but rather the future-sample failure probability   𝑅 𝜇 (𝑊𝑚 ) := Pr 𝑋 ★ ∉ 𝑊𝑚 , 𝑊𝑚 := span(𝑋 1, . . . , 𝑋𝑚 ). 𝑋 ★ ∼𝜇

The distinction can be substantial. Consider, for example, a distribution on two independent vectors satisfying Pr[𝑋 = 𝑒 1 ] = 1 − 2−𝜆 ,

Pr[𝑋 = 𝑒 2 ] = 2−𝜆 .

Generating the entire support span span{𝑒 1, 𝑒 2 } requires observing the exponentially rare direction 𝑒 2 . In contrast, the one-dimensional span span{𝑒 1 } already contains an independently generated future sample with probability 1 − 2−𝜆 . Hence full-span recovery can be far stronger than what cryptanalysis actually requires: The attacker need not learn the entire algebraic span; it only needs to learn where future ciphertexts are likely to lie. A statistical view of linear cryptanalysis. This distinction connects algebraic cryptanalysis to distribution-free learning. Stable sample-compression theory provides high-probability guarantees for the population error of hypotheses reconstructed from small stable compression sets [8]. More recently, related learning-theoretic work has explicitly considered algorithms that use sampled vectors to obtain linear subspaces covering most of an underlying arbitrary distribution [13]. These results, however, are not cryptanalytic statements: they do not consider observations (𝑋, 𝐴𝑋 ) generated by a hidden secret action, coefficient transfer to future cryptographic targets, or formal consequences for public-key security. This paper studies precisely this intersection: Linear-decomposition cryptanalysis ∩ distribution-free learning ∩ formal PKE security. We ask whether the public sampling-and-evaluation capability already required for honest encryption can, by itself, reveal the effect of a fixed secret linear map on future ciphertexts. Our results. We formalize this question through a public paired sampler induced by public states and secret actions Pair(𝜌) = (𝑋 𝜌 , 𝑌𝜌 ),

𝑌𝜌 = 𝐴𝑋 𝜌 ,

where 𝜌 follows an arbitrary public distribution and the adversary is given neither 𝐴 nor an explicit generating set or basis for the reachable subspace. For the span of target distribution 𝜇, 𝑊𝜇 := span(supp 𝜇),

𝑟 𝜇 := dim𝑊𝜇 ,

we call 𝑟 𝜇 the sampled orbit dimension. Our first result gives a distribution-free one-shot guarantee. For independent 𝑋 1, . . . , 𝑋𝑚 , 𝑋 ★ ∼ 𝜇,   𝑟𝜇 Pr 𝑋 ★ ∈ span(𝑋 1, . . . , 𝑋𝑚 ) ≥ 1 − . 𝑚+1 Consequently, the corresponding transported value 𝑌 ★ = 𝐴𝑋 ★ is recovered with the same probability by classical coefficient transfer. In particular, 2𝑟 𝜇 − 1 public samples already give success probability at least 1/2, without any uniformity or anti-concentration assumption on 𝜇. We then strengthen this one-shot statement to an offline-tofuture guarantee. Viewing the rank-increasing samples as a stable compression set yields, with probability at least 1 − 𝛿 over the preprocessing samples,   𝑟 𝜇 + log(1/𝛿) 𝑅 𝜇 (𝑊𝑚 ) = 𝑂 . 𝑚 Thus   𝑟 𝜇 + log(1/𝛿) 𝑚 =𝑂 𝜀 public samples suffice for a fixed learned span to recover the transported value for at least a 1 − 𝜀 fraction of future encryption randomness, with confidence 1 − 𝛿. We complement this upper bound with matching lower bounds for the distribution-free sampled-span problem and obtain the minimax characterization   𝑟 + log(1/𝛿) . 𝑚★span (𝑟, 𝜀, 𝛿) = Θ 𝜀 The optimality statement concerns sampled-span coverage; we do not claim a lower bound for all possible cryptanalysis. Finally, we translate these statistical guarantees into a formal PKE impossibility result. For schemes in which a publicly samplable exact linear transport 𝑌𝜌 = 𝐴sk𝑋 𝜌 determines the decryption-critical payload information, polynomial sampled-orbit dimension implies a polynomial-time IND–CPA adversary with constant advantage. Hence hiding an explicit algebraic generating set is insufficient: public sampling alone can already reveal the secret transport on enough of the ciphertext distribution to violate semantic security. A concrete break of a twisted–skew PKE.. We instantiate the framework against the probabilistic PKE proposed by de la Cruz, MartínezMoro, Muñoz-Ruiz, and Villanueva-Polanco [5]. Their construction is based on twisted–skew group rings and uses a generally nonassociative multiplication. Nevertheless, keeping the multiplication order fixed, we show that the decryption-critical map is F𝑞 -linear and that the public protocol itself provides exactly the paired samples required by our attack. This yields a direct sampler-only attack on the Computational Twisted–Skew Problem (CTSP) underlying the construction and, consequently, on the PKE. For the proposed setting with |𝐺 | = 2𝑛, the ambient F𝑞 dimension is 4𝑛. Our distribution-free bound therefore implies that 8𝑛 − 1 independently generated public samples suffice to recover a fresh CTSP target with probability at least 1/2, yielding constant IND–CPA advantage for the PKE. To the best of our knowledge, we are unaware of a prior work that gives an explicit

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

cryptanalysis of the CTSP or Algorithms 6–8 of this exact 2024 construction. We nevertheless state this claim cautiously: closely related linear-system attacks on two-sided multiplication protocols have been studied, including the recent work of Otero Sanchez [14], and classical basis-based linear-decomposition ideas may also be adaptable to the construction. Our claim is therefore not that linear decomposition itself is new, nor that sampler access is necessary to break the scheme, but that honest public sampling alone suffices under an arbitrary induced distribution and admits an explicit finite-sample security analysis.

(3) Sender initialization. The sender obtains (𝑣, 𝑤, D) from the public interface. (4) Fresh sampling. The sender samples 𝜌 ← D and computes 𝑋 𝜌 := 𝐵 𝜌 𝑣 and sender’s local shared key 𝑌𝜌 := 𝐵 𝜌 𝑤. (5) Transmission. The sender transmits 𝑋 𝜌 to the receiver. (6) Receiver key derivation. The receiver computes reciever’s shared key 𝐴𝑋 𝜌 using the secret map. Correctness requires the key-transport relation 𝐵 𝜌 𝑤 = 𝐴(𝐵 𝜌 𝑣)

(1)

for every valid 𝜌. Consequently, the two honest computations agree: Contributions. Our contributions can be summarized as follows. • Sampler-only linear cryptanalysis. We formulate public linear key transport through paired samples (𝑋 𝜌 , 𝑌𝜌 ) with 𝑌𝜌 = 𝐴𝑋 𝜌 and characterize the distribution-free futureciphertext coverage of the sampled span. The resulting sample complexity is   𝑟 + log(1/𝛿) Θ 𝜀 for the sampled-span problem. • Formal PKE consequence. We show that publicly samplable exact linear key transport of polynomial sampled orbit dimension is incompatible with IND–CPA security whenever the transported value suffices to recover the encryption payload. • Concrete cryptanalysis. We instantiate the framework against the 2024 twisted–skew group-ring PKE, directly attack its CTSP assumption using only publicly generated samples, and derive explicit plaintext-recovery and IND– CPA consequences.

2

Preliminaries and Attack Setup

Figure 1 summarizes the complete setup used in the paper. Its lefthand side shows how an honest sender and receiver obtain the same transported key through the public interface; its right-hand side shows how an adversary replaces the secret computation by public sampling, linear decomposition, and coefficient transfer. We formalize these two flows in that order.

2.1

Honest public linear key transport

Let F be a field and let 𝑉 be an 𝑁 -dimensional vector space over F. All vector-space operations and linear-system computations are assumed efficient in the natural representation of 𝑉 . In the cryptographic applications below, F is finite. The motivating honest protocol uses public vectors 𝑣, 𝑤 ∈ 𝑉 , a secret linear map 𝐴 ∈ EndF (𝑉 ), and a publicly samplable family of linear maps, denoted as sampling-and-evaluation process, 𝐵 𝜌 ∈ EndF (𝑉 ),

𝜌 ← D,

where D is an arbitrary distribution over public sender randomness. The protocol shown on the left of Figure 1 proceeds as follows. (1) Receiver setup. The receiver chooses a public base point 𝑣 ∈ 𝑉 and a secret linear map 𝐴. (2) Public key. The receiver computes 𝑤 := 𝐴𝑣 and publishes (𝑣, 𝑤) together with the public sampling-and-evaluation interface for 𝐵 𝜌 .

𝐵 𝜌 𝑤 = 𝐴𝑋 𝜌 . |{z} |{z} sender key

receiver key

Commutation 𝐴𝐵 𝜌 = 𝐵 𝜌 𝐴 is sufficient for (1), because 𝑤 = 𝐴𝑣, but only the displayed transport relation is required. The analysis also covers protocols in which the two public values are not syntactically obtained by applying the same map 𝐵 𝜌 to two fixed vectors. We therefore retain the following more general interface. An honest sender, and hence an adversary, can sample 𝜌 ← D and run a public procedure Pair(𝜌) = (𝑋 𝜌 , 𝑌𝜌 ) ∈ 𝑉 × 𝑉 . There exists a fixed secret linear map 𝐴 ∈ EndF (𝑉 ) such that 𝑌𝜌 = 𝐴𝑋 𝜌

(2)

for every valid 𝜌. The protocol above realizes this abstraction by setting Pair(𝜌) = (𝐵 𝜌 𝑣, 𝐵 𝜌 𝑤). The procedure need not reveal 𝐴, an algebraic generating set, or a basis for the reached subspace. Let 𝜇 denote the distribution of 𝑋 𝜌 for 𝜌 ← D. Its sampled orbit subspace and sampled orbit dimension are
𝑊𝜇 := spanF supp(𝜇) , 𝑟 𝜇 := dimF 𝑊𝜇 ≤ 𝑁 .

2.2

Sampler-only linear-decomposition attack

The right-hand side of Figure 1 turns the honest public interface into an attack. The adversary performs the following three steps. i.i.d.

(1) Public paired sampling. Sample 𝜌 1, . . . , 𝜌𝑚 ∼ D, evaluate as {𝐵 𝜌𝑖 }𝑚 𝑖=1 and compute (𝑋𝑖 , 𝑌𝑖 ) := Pair(𝜌𝑖 ),

𝑖 ∈ [𝑚].

(2) Linear decomposition. On receiving a fresh target 𝑋 ★, test whether it lies in 𝑊𝑚 := spanF {𝑋 1, . . . , 𝑋𝑚 }. If so, Gaussian elimination returns 𝛼 1, . . . , 𝛼𝑚 ∈ F such that 𝑚 ∑︁ 𝑋★ = 𝛼 𝑖 𝑋𝑖 . 𝑖=1

(3) Key recovery. Transfer the same coefficients to the second components and output 𝑚 ∑︁ 𝑌b★ := 𝛼𝑖 𝑌𝑖 . 𝑖=1

Chen and Zhou

Figure 1: Honest linear key transport (left and center) and the sampler-only linear-decomposition attack (right). The adversary learns the transported value on a covered target without recovering the secret map. Note that in the image, we use 𝐵 𝜌 ∼ D as a short-hand of sampling-and-evaluation process. The algebraic justification is the classical linear-decomposition principle: linear relations among public states transfer through the unknown fixed linear map. This mechanism underlies the linear decomposition attack of Myasnikov and Roman’kov [12] and algebraic-span cryptanalysis [3]. 𝑚 satisfy 𝑌 = Lemma 2.1 (Coefficient transfer). Let (𝑋𝑖 , 𝑌𝑖 )𝑖=1 𝑖 𝐴𝑋𝑖 for a fixed linear map 𝐴 ∈ EndF (𝑉 ). Suppose a target pair (𝑋 ★, 𝑌 ★) satisfies 𝑚 ∑︁ 𝑌 ★ = 𝐴𝑋 ★, 𝑋★ = 𝛼 𝑖 𝑋𝑖 𝑖=1

for coefficients 𝛼 1, . . . , 𝛼𝑚 ∈ F. Then the adversary recovers the target value without recovering 𝐴: 𝑚 ∑︁ 𝑌★ = 𝛼𝑖 𝑌𝑖 . (3)

The proof is given in Appendix C.2. Remark 1. Taking 𝑚 = 2𝑟 𝜇 − 1 in Proposition 2.2 gives recovery probability at least 1/2. More generally, 𝑚 = 𝑂 (𝑟 𝜇 /𝜀) gives one-shot failure probability at most 𝜀. We next strengthen this pointwise statement to a high-probability certificate on the failure rate over all future samples and establishes the optimal sample complexity.

3

We now move from one-shot recovery to a distribution-free finitesample analysis. The central observation is that sequentially retaining only rank-increasing samples defines a stable sample compression scheme whose compression size is exactly the empirical sampled-orbit dimension. This connects sampler-only linear cryptanalysis to stable compression theory.

3.1

𝑖=1

The proof is given in Appendix C.1. Let the dimension of public sample span

Main Results

A distribution-free future-coverage certificate

Consider the following greedy compression rule. Process 𝑋 1, . . . , 𝑋𝑚 in order and retain 𝑋𝑖 if and only if

b 𝑟𝑚 := dim𝑊𝑚

𝑋𝑖 ∉ span(𝑋 1, . . . , 𝑋𝑖 −1 ).

and define the fresh-sample failure probability by 𝑅 𝜇 (𝑊 ) := Pr [𝑋 ∉ 𝑊 ].

Denote the retained set as

𝑋 ∼𝜇

for any subspace 𝑊 ⊆ 𝑉 . Thus 𝑅 𝜇 (𝑊𝑚 ) is the probability that a fresh public sample falls outside the span.

2.3

𝜅 (𝑆𝑚 ) ⊆ 𝑆𝑚 := {𝑋 1, . . . , 𝑋𝑚 }. By construction, 𝜅 (𝑆𝑚 ) keeps the dimension and span, namely |𝜅 (𝑆𝑚 )| = b 𝑟𝑚 = dim𝑊𝑚 ,

A one-shot distribution-free attack

Classical linear-decomposition cryptanalysis typically constructs an exact orbit span from publicly known generators [3, 12]. Here we instead require no assumption on the distribution 𝜇. i.i.d.

Proposition 2.2 (One-shot attack). Let 𝑋 1, . . . , 𝑋𝑚 , 𝑋 ★ ∼ 𝜇, with sampled orbit dimension 𝑟 𝜇 . Then   𝑟𝜇 Pr 𝑋 ★ ∈ span(𝑋 1, . . . , 𝑋𝑚 ) ≥ 1 − . (4) 𝑚+1 Consequently, using the paired samples (𝑋𝑖 , 𝑌𝑖 ) and Lemma 2.1, the target 𝑌 ★ can be recovered with probability at least 𝑟𝜇 . 1− 𝑚+1

span(𝜅 (𝑆𝑚 )) = 𝑊𝑚 .

(5)

Theorem 3.1 (Distribution-free sampler-only certificate). i.i.d. Let 𝑋 1, . . . , 𝑋𝑚 ∼ 𝜇. Then, for every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿 over the 𝑚 training samples, the fresh-sample failure probability satisfies 4  𝑒 𝑅 𝜇 (𝑊𝑚 ) ≤ 6b 𝑟𝑚 + ln . (6) 𝑚 𝛿 Consequently, since b 𝑟𝑚 ≤ 𝑟 𝜇 , it is further bounded by 4  𝑒 𝑅 𝜇 (𝑊𝑚 ) ≤ 6𝑟 𝜇 + ln . (7) 𝑚 𝛿

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

𝑚 , an Therefore, after observing 𝑚 public paired samples (𝑋𝑖 , 𝑌𝑖 )𝑖=1 ★ adversary can recover the transported value 𝑌 for at least a 1 − 𝑅 𝜇 (𝑊𝑚 ) fraction of fresh samples with probability at least 1 − 𝛿.

The proof is given in Appendix D.1.

3.2

Optimal sample complexity

The preceding theorem gives an 𝑂 (𝑟 𝜇 /𝜀) upper bound. We next show a matching lower bound, which indicates that this dependence is unavoidable for arbitrary sampling distributions. For integers 𝑟 ≥ 1 and parameters 𝜀, 𝛿 ∈ (0, 1), define the minimax distribution-free sampled-span complexity 𝑚★span (𝑟, 𝜀, 𝛿) :=  min 𝑚 :

where the probability is over the encryption and recovery randomness. We refer to (13) as the recoverable-payload condition. The masking construction 𝐶 payload = 𝑚 ⊕ 𝐻𝜆 (𝑌𝜌 ) is one special case. The condition also covers KEM–DEM case with encryption Encsym and decryption Decsym , namely 𝐾 = KDF𝜆 (𝑌𝜌 ),

𝐶 payload = Encsym (𝐾, 𝑚; 𝜎),

since the recovery algorithm can derive 𝐾 from 𝑌𝜌 and run Decsym . sup

Pr 𝑚

𝜇:dim span(supp 𝜇 ) ≤𝑟 𝑆𝑚 ∼𝜇



  𝑅 𝜇 (𝑊𝑚 ) > 𝜀 ≤ 𝛿 .

Theorem 3.2 (Optimal distribution-free sample complexity). For 𝑟 ≥ 2, 𝜀 ∈ (0, 1/4), and 𝛿 ∈ (0, 1/2),   𝑟 + ln(1/𝛿) . 𝑚★span (𝑟, 𝜀, 𝛿) = Θ 𝜀 More explicitly, from the preceding theorem,    𝑒 4 𝑚★span (𝑟, 𝜀, 𝛿) ≤ 6𝑟 + ln , 𝜀 𝛿 while every distribution-free guarantee must satisfy 𝑟 −1 𝑚★span (𝑟, 𝜀, 𝛿) > 8𝜀 and ln(1/𝛿) 𝑚★span (𝑟, 𝜀, 𝛿) ≥ 4𝜀 up to integer rounding.

(8)

(9)

(10)

IND-CPA impossibility for public linear key transport

We now translate the sampled-span phenomenon into a generic cryptographic impossibility result. Consider a family of public-key encryption schemes indexed by the security parameter 𝜆. The public key specifies a finitedimensional vector space 𝑉𝜆 , a distribution D𝑝𝑘 over public randomness, and a public polynomial-time paired-sample procedure Pair(𝑝𝑘; 𝜌) = (𝑋 𝜌 , 𝑌𝜌 ),

𝜌 ← D𝑝𝑘 .

Assume there is a fixed secret linear map 𝐴𝑠𝑘 ∈ EndF (𝑉𝜆 ) such that 𝑌𝜌 = 𝐴𝑠𝑘 𝑋 𝜌

Theorem 3.3 (IND-CPA no-go theorem for recoverable payloads). Suppose the scheme (12) satisfies the public linear-transport condition (11) and the recoverable-payload condition (13). Let  𝑟 (𝑝𝑘) := dim span 𝑋 𝜌 : 𝜌 ∈ supp(D𝑝𝑘 ) . Assume that there is a publicly known polynomial 𝑅(𝜆) such that 𝑟 (𝑝𝑘) ≤ 𝑅(𝜆) for all valid public keys, and that paired sampling and linear algebra in 𝑉𝜆 are polynomial-time operations. Then there exists a probabilistic polynomial-time adversary with IND-CPA advantage at least 1 − 𝜈 (𝜆). 4 Consequently, the scheme is not IND-CPA secure. Under perfect payload correctness, the advantage is at least 14 . The proof is given in Appendix D.3.

The proof is given in Appendix D.2.

3.3

polynomial-time algorithm RecoverPayload and a negligible function 𝜈 such that, for every valid public key and every message 𝑚, the probability of recovery failure is negligible, namely  
Pr RecoverPayload 𝑝𝑘, 𝐶 payload, 𝑌𝜌 = 𝑚 ≥ 1 − 𝜈 (𝜆), (13)

(11)

for every valid 𝜌. Let the encryption randomness be (𝜌, 𝜎), where 𝜌 ← D𝑝𝑘 determines the public linear-transport component and 𝜎 denotes any additional randomness used to form the payload. We consider ciphertexts of the general form
Enc(𝑝𝑘, 𝑚; 𝜌, 𝜎) = 𝑋 𝜌 , 𝐶 payload , (12) and the transported value 𝑌𝜌 is sufficient to recover the plaintext from the payload. Formally, assume there is a public probabilistic

Remark 2 (Stronger future-decryption interpretation). Theorem 3.3 requires only the constant-success one-shot bound. Theorem 3.1 gives a stronger interpretation: after   𝑟 (𝑝𝑘) + ln(1/𝛿) 𝑚 =𝑂 𝜀 self-generated public samples, with probability at least 1 − 𝛿 over the preprocessing samples, the same sampled span permits exact recovery of the transported value and hence payload recovery for at least a 1 − 𝜀 fraction of all future encryption randomness, up to the negligible recovery error 𝜈 (𝜆).

4

Application to Twisted–Skew Group-Ring Protocols

We instantiate the sampler-only framework against the computational assumption and probabilistic PKE of twisted–skew groupring protocols proposed by de la Cruz, Martínez-Moro, Muñoz-Ruiz, and Villanueva-Polanco [5]. The attack uses only public sampling and evaluation together with linear algebra over F𝑞 .

4.1

The 2024 construction

Let 𝜃 ,𝛼 𝜆

R = F𝑞𝜎2

𝐺

be the twisted–skew group-ring space of the scheme. We reproduce only Algorithms 6–8 and their correctness relation. Writing the original two-sided action with explicit evaluation order as 𝜓 ((𝑎, 𝛾), 𝑥) := (𝑎𝑥)𝛾,

Chen and Zhou

Alice samples sk = (𝑎 1, 𝛾 1 ) and publishes pk = (𝑎 1ℎ)𝛾 1 . For fresh encryption randomness 𝜌 = (𝑎 2, 𝛾 2 ), encryption computes 𝑋 𝜌 := 𝑐 1 = (𝑎 2ℎ)𝛾 2 and 𝑐 2 = 𝑚 + 𝑌𝜌 , 𝑌𝜌 := (𝑎 2 pk)𝛾b2 . Here and below, the displayed parentheses specify the order of multiplication; we do not reassociate products. Decryption subtracts (𝑎 1𝑐 1 )𝛾b1 from 𝑐 2 . The correctness theorem of the construction establishes, for every valid encryption randomness, (𝑎 1𝑐 1 )𝛾b1 = (𝑎 2 pk)𝛾b2 .

(14)

These are exactly the quantities computed in Algorithms 6–8 and related by Theorem 3 of the original paper [5].

4.2

Fixed linear transport and self-generated pairs

Define the secret-dependent, fixed-parenthesis map Ask : R −→ R,

Ask (𝑥) := (𝑎 1𝑥)𝛾b1 .

(15)

Lemma 4.1 (Twisted–skew linear transport). The map Ask is F𝑞 -linear. Moreover, every honest encryption randomness 𝜌 = (𝑎 2, 𝛾 2 ) satisfies 𝑌𝜌 = Ask (𝑋 𝜌 ). The proof is given in Appendix E.1. Importantly, the proof uses only F𝑞 -bilinearity with the parentheses in (15); it never invokes associativity.

4.3

Direct attack on the CTSP assumption

The original paper defines the Computational Twisted–Skew Product (CTSP) through its Algorithm 2. The challenger independently samples (𝑎 1, 𝛾 1 ), (𝑎 2, 𝛾 2 ) ← SK and gives the adversary 𝑝𝑘 1 = 𝜓 ((𝑎 1, 𝛾 1 ), ℎ),

𝑝𝑘 2 = 𝜓 ((𝑎 2, 𝛾 2 ), ℎ).

The target is

Corollary 4.2 (Sampler-only solution of CTSP). Given a CTSP instance (𝑝𝑘 1, 𝑝𝑘 2 ) and 𝑚 independently generated public pairs (𝑋𝑖 , 𝑌𝑖 ) as above, a polynomial-time adversary recovers the CTSP target with probability at least 𝑟 𝑝𝑘1 Pr[b 𝑘 = 𝑘] ≥ 1 − . (16) 𝑚+1 If |𝐺 | = 2𝑛, then 𝑟 𝑝𝑘1 ≤ 4𝑛; hence 𝑚 = 8𝑛 − 1 gives CTSP success probability at least 1/2. In particular, the CTSP assumption does not hold whenever this ambient dimension and the public operations are polynomial in the security parameter, as in the proposed parameter families. The proof is given in Appendix E.2. The samples use only the public sampling-and-evaluation operations available to an honest participant; no explicit generators or precomputed basis of the sampled action space are required.

4.4

The PKE challenge is precisely the CTSP computation followed ★ by additive masking: set 𝑝𝑘 1 = pk, 𝑝𝑘 2 = 𝑋 ★ = 𝑐 ★ 1 , and 𝑘 = 𝑌 . ★ ★ ★ The challenge payload is 𝑐 2 = 𝑚 + 𝑌 . Moreover, because the message space is additive and encryption is public, an adversary can generate the CTSP training pairs by computing Enc(pk, 0; 𝜌𝑖 ) = (𝑋𝑖 , 𝑐 2,𝑖 ),

Corollary 4.3 (Sampler-only break of the 2024 PKE). Given 𝑚 independently generated encryptions of zero, a polynomial-time adversary recovers the plaintext of an independent fresh ciphertext with probability at least 𝑟 pk 1− . (17) 𝑚+1 If |𝐺 | = 2𝑛, then 𝑟 pk ≤ 4𝑛. Consequently, 𝑚 = 8𝑛 − 1 self-generated encryptions of zero give plaintext-recovery probability at least 1/2 and IND–CPA advantage at least 1/4 under the convention

𝑘 = 𝜓 ((𝑎 2, 𝛾b2 ), 𝑝𝑘 1 ). A𝑝𝑘1 (𝑥) := (𝑎 1𝑥)𝛾b1

𝑘 = A𝑝𝑘1 (𝑝𝑘 2 ). The adversary can independently sample (𝑏𝑖 , 𝜂𝑖 ) ← SK and publicly compute 𝑋𝑖 := 𝜓 ((𝑏𝑖 , 𝜂𝑖 ), ℎ),

𝑌𝑖 := 𝜓 ((𝑏𝑖 , 𝜂b𝑖 ), 𝑝𝑘 1 ).

The same identity gives 𝑌𝑖 = A𝑝𝑘1 (𝑋𝑖 ). Let
𝜇𝑝𝑘1 := Law 𝜓 ((𝑏, 𝜂), ℎ) , (𝑏, 𝜂) ← SK, and define
𝑟 𝑝𝑘1 := dimF𝑞 spanF𝑞 supp 𝜇𝑝𝑘1 .

𝑐 2,𝑖 = 𝑌𝑖 = Ask (𝑋𝑖 ).

These are self-generated public encryptions. They query neither the secret key nor a decryption oracle. Write 𝑟 pk := 𝑟 𝑝𝑘1 for the corresponding effective rank.

AdvIND-CPA = Pr[𝑏 ′ = 𝑏] −

For a fixed 𝑝𝑘 1 , write

for the secret-dependent map associated with its hidden generating pair. Lemma 4.1 and the correctness identity give

Plaintext recovery and IND–CPA consequence

1 . 2

The proof is given in Appendix E.3. The 8𝑛 − 1 count is a worstcase ambient-dimension guarantee: the effective rank 𝑟 pk may be substantially smaller. Theorem 3.1 also gives a high-probability certificate for the fraction of all future ciphertexts covered by the learned span, without assuming uniformity, coordinate independence, or anti-concentration.

4.5

Relation to prior linear-decomposition attacks

Random sampling in linear-decomposition cryptanalysis is not new. Roman’kov observed that random vectors may replace an explicitly constructed basis under a protocol-specific uniform-sampling model [17]. Earlier linear-decomposition and algebraic-span attacks likewise establish the coefficient-transfer principle [3, 12]. Our contribution here is instead to use only the distribution induced by

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

honest public sampling and encryption, allow that distribution to be arbitrary, and quantify how a finite sampled span covers an independently generated target. Some generic two-sided-multiplication theorems impose hypotheses that differ from this construction, such as associativity or explicit public generators and bases for the relevant action spaces [16]. Later attacks on earlier twisted-dihedral or two-sided-action proposals likewise use scheme-specific hypotheses [14, 20]. These differences mean that such results do not apply verbatim; they do not imply that classical basis-based linear-decomposition methods cannot be adapted here. We therefore do not claim that sampleronly access is necessary to break the construction. To the best of our knowledge, we are unaware of a prior explicit cryptanalysis of the CTSP or Algorithms 6–8 of this exact 2024 construction. Our contribution is a sampler-only, distribution-free attack requiring no explicit generators or precomputed action basis, with a finite-sample CTSP guarantee and formal plaintext-recovery and IND–CPA consequences. We do not claim that coefficient transfer or random-spanning ideas themselves are new.

5

Check F19 -linearity Paired-sample transport Decryption correctness

Trials

Violations

200 200 200

0 0 0

Experimental Evaluation

We organize the evaluation as one four-step validation of the cryptanalytic story developed above: valid setup −→ end-to-end break −→ explanation of the native threshold −→ separation between rank and probability-mass coverage. The experiments use exact finite-field arithmetic; no numerical tolerance is involved in an equality, rank, span-membership, or plaintext-recovery test. We implement the twisted–skew product and adjunct with the evaluation order used by the construction, represent each ring element by its 4𝑛 coordinates over F19 , and use the dihedral parameter sets 𝑛 ∈ {20, 23, 32}. For each 𝑛, Experiments 2–4 use 20 independently generated public setups. The exact sampled-orbit rank 𝑟 pk is computed separately for every public ℎ by evaluating the bilinear sampler map on bases of its two input spaces. For the native-sampler curves, the sample budget ranges from 𝑟 pk − 10 to 𝑟 pk + 10. At each budget we generate five independent learned spans per setup, increased to 25 spans whenever |𝑚 −𝑟 pk | ≤ 2, and test 50 independent future ciphertexts against each span. Shaded regions and error bars are 95% percentile intervals from a two-stage bootstrap that resamples public setups and then learned spans within each setup. Thus ciphertexts tested against the same span are not incorrectly treated as independent statistical units.

5.1

Table 1: Exact algebraic validation for 𝑝 = 𝑞 = 19, 𝑛 = 20, and dimF19 R = 80.

Does the implementation realize the attack model?

The first step checks that the concrete implementation has exactly the structure required by the theory. For the 𝑛 = 20 setup, we independently test three identities over 200 trials: F19 -linearity of the fixed secret map, the paired-sample identity Ask (𝑋 𝜌 ) = 𝑌𝜌 , and encryption/decryption correctness. Each linearity trial samples independent 𝑥, 𝑧 ∈ R and 𝛼, 𝛽 ∈ F19 and checks Ask (𝛼𝑥 + 𝛽𝑧) = 𝛼Ask (𝑥) + 𝛽Ask (𝑧).

Figure 2: End-to-end plaintext recovery under the native protocol sampler. The horizontal coordinate is centered at the exact rank of each public setup. Shading gives 95% hierarchicalbootstrap intervals. The other tests use freshly sampled valid protocol randomness and messages. Table 1 reports no violation. This experiment is not evidence from approximate numerical behavior: it verifies equality of the full ring elements. It therefore confirms that the implemented PKE exposes the fixed linear transport assumed in Sections 2.1 and 4.2.

5.2

Does the sampler-only attack recover plaintexts?

Having validated the setup, we next test the security consequence end to end. For every public key, the adversary generates 𝑚 public encryptions of zero, uses their pairs (𝑋𝑖 , 𝑌𝑖 ) to build an incremental linear-transport basis, and attacks fresh encryptions of independently sampled messages. When a fresh 𝑋 ★ enters the learned span, the implementation transfers the exact decomposition coefficients ★ to obtain 𝑌 ★ and outputs 𝑐 ★ 2 −𝑌 . Figure 2 shows a sharp and consistent transition across all three parameter sizes. At 𝑚 = 𝑟 pk − 1, recovery is only 5.1–5.3%. At 𝑚 = 𝑟 pk , it rises to 95.47%, 94.81%, and 94.48% for 𝑛 = 20, 23, 32, respectively; one further sample raises all three rates above 99.6%, and two further samples give 100% in the recorded trials. Most importantly, every recorded span hit produced the exact challenge plaintext: the empirical conditional probability Pr[𝑚 b = 𝑚 | 𝑋★ ∈ 𝑊𝑚 ] is one throughout the experiment. Thus the sampled-span event is not merely a geometric diagnostic; it triggers an actual decryption of the concrete scheme using only public encryptions.

Chen and Zhou

5.3

Why is the native recovery threshold sharp?

The third step explains the transition rather than repeating the attack. We first compute the exact sampled-orbit rank for each of the 60 public setups. As Figure 3 shows, the native sampled orbit is almost always the full ambient space: 56 of the 60 setups have 𝑟 pk = 4𝑛, while the remaining four have codimension two. The mean ranks are 79.8 of 80, 91.9 of 92, and 127.9 of 128 for 𝑛 = 20, 23, 32.

Figure 4: Fraction of the exact sampled-orbit rank learned from native samples. The native recovery transition occurs only as this fraction approaches one.

Figure 3: Exact native sampled-orbit rank over 20 independent public setups per parameter size. The dashed diagonal is the ambient limit 4𝑛; open diamonds mark means. We then measure rank acquisition and future coverage using new native samples, independently of the plaintext-recovery experiment. At 𝑚 = 𝑟 pk − 1, the learned spans already contain between 98.74% and 99.22% of the exact rank, yet cover only 4.94–5.37% of future samples. At 𝑚 = 𝑟 pk , the mean rank fraction exceeds 99.93% and future coverage rises to 94.98–95.44%. Figure 4, read together with Figure 2, therefore identifies the mechanism: recovery transition ⇐= future-coverage transition ⇐= acquisition of the last native rank directions. This behavior is consistent with a comparatively spread-out native sampler: missing even one of its final directions leaves substantial future probability mass uncovered. Full-span acquisition therefore explains the location of the native threshold, but it does not yet establish that full rank is necessary for an arbitrary encryptioninduced distribution.

5.4

Is full-span recovery fundamentally necessary?

The final step isolates that distributional question with two controlled synthetic stress tests over valid protocol randomness. These samplers are not proposed as models of the native 2024 distribution. The moderate sampler places 80% of its mass uniformly on a fixed pool of 16 valid ephemeral randomness pairs and retains the native

sampler with probability 20%. The strong sampler places 98% of its mass on a pool of four valid pairs and retains the native sampler with probability 2%. Because both native components are strictly positive, the two synthetic distributions retain the full native algebraic support and hence the same exact 𝑟 pk ; only the allocation of probability mass changes. Figure 5 displays the resulting separation. At 𝑚 = 𝑟 pk , the moderate sampler learns only 39.6%, 37.1%, and 32.5% of the exact rank for 𝑛 = 20, 23, 32, but already covers 78.8–80.1% of future samples. The strong sampler is more striking: it learns only 7.1%, 6.3%, and 5.1% of the exact rank while covering 97.88–98.03% of future samples. Its rank deficit grows with 𝑛, yet its attack-relevant coverage remains essentially the 98% probability mass concentrated on the hot pool. The native experiment and the stress tests therefore answer different questions. The former explains why this implementation exhibits a threshold near 𝑚 = 𝑟 pk ; the latter demonstrates that this is a property of the native distribution, not a general prerequisite of coefficient-transfer attacks. The empirical conclusion matches the quantity controlled by our theorems: Full-span recovery explains the native experiment, but it is not generally required for successful future-ciphertext attacks.

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

Figure 5: Learned rank fraction versus future coverage at 𝑚 = 𝑟 pk . Native values come from Experiment 3; the moderate and strong hot-pool samplers are controlled synthetic stress tests. Error bars give 95% hierarchical-bootstrap intervals.

6 Discussion 6.1 Implications for Public-Key Encryption Design Our results suggest a simple design lesson for algebraic publickey encryption: security should not be evaluated only in terms of whether the underlying secret action, hidden generators, or full algebraic orbit can be recovered. If honest public operations expose sufficiently many examples of a fixed exact linear transport, then an adversary may recover the effect of the secret action on future ciphertexts without reconstructing the action itself. The attack studied in this paper relies on three structural ingredients: a publicly samplable source of paired observations, a fixed low-dimensional exact linear transport across those observations, and a ciphertext payload that becomes recoverable once the transported value is known. Preventing the present attack therefore requires breaking at least one of these ingredients. In particular, merely hiding an explicit generating set or making full-span reconstruction inconvenient is not sufficient. Our analysis shows that the relevant cryptanalytic quantity is the probability mass of future ciphertexts covered by the sampled span. The nonuniform stress tests further demonstrate that this coverage may become large even when the adversary has recovered only a small fraction of the full algebraic rank. Hence increasing algebraic support alone does not necessarily address the vulnerability if most encryption probability remains concentrated on a much smaller learnable region.

6.2

Limitations and Scope

Our results concern exact linear key transport. The generic attack assumes that publicly generated pairs satisfy a fixed relation of the form 𝑌𝜌 = 𝐴𝑋 𝜌 over a finite-dimensional vector space. The analysis therefore does not directly cover schemes in which the corresponding relation is nonlinear, depends essentially on fresh hidden randomness, or is only approximately linear.

Table 2: Design implications of the sampler-only attack. Vulnerable ingredient

Possible design response

Public paired sampling

Avoid exposing publicly evaluable pairs that reveal the same secret-dependent transport across fresh randomness. Introduce genuinely nonlinear, randomness-dependent, or otherwise non-transferable secret transformations. Ensure that the publicly sampled states do not lie in a polynomial-dimensional linear representation accessible to the adversary. Avoid constructions in which knowledge of the transported value alone enables public recovery of the plaintext or session key.

Fixed exact linear transport Low effective dimension

Recoverable payload from the transported value

Likewise, the optimality result in Section 3 characterizes the distribution-free sample complexity of the sampled-span coverage problem. It does not establish a lower bound against every possible cryptanalytic algorithm. An adversary exploiting additional algebraic information, protocol structure, side information, or a different representation may in principle require fewer samples. The concrete experiments are intended to validate the attack mechanism and its distributional interpretation for the twisted– skew construction studied in this paper. The synthetic non-uniform samplers are controlled stress tests over valid protocol randomness rather than models of the native randomness distribution. Their purpose is to isolate the distinction between algebraic rank and future-ciphertext probability mass, not to claim that the original 2024 scheme uses such skewed distributions. Finally, our concrete cryptanalysis does not imply that sampleronly access is the only possible way to attack the twisted–skew construction. Classical basis-based linear-decomposition or other scheme-specific algebraic techniques may also be adaptable. Our contribution is instead to show that the public sampling capability alone already suffices, under arbitrary induced distributions, and

Chen and Zhou

to quantify this fact through explicit finite-sample guarantees and formal security consequences. Extending the analysis to noisy or approximate transport is a natural next step. In that setting, coefficient transfer introduces accumulated error, and the success of the attack may depend on the conditioning of the sampled representation, the norm of the decomposition coefficients, and the error tolerance of the payloadrecovery mechanism.

7

Related Work

Algebraic actions in public-key cryptography. Algebraic group and semigroup actions have long provided a framework for constructing public-key protocols beyond classical number-theoretic settings. The Ko–Lee protocol used commuting subgroup actions in braid groups [9], while Anshel, Anshel, and Goldfeld proposed a related noncommutative approach based on conjugation and commutators [1]. Maze, Monico, and Rosenthal later formulated Diffie–Hellman-type key exchange directly through semigroup actions on finite sets [10]. These constructions motivate a general security question that is central to our work: even when recovering the secret algebraic action is difficult, can its effect on a fresh public state be reconstructed from publicly available linear information? Linear-algebraic and linear-decomposition cryptanalysis. A substantial line of work shows that the answer can be positive. Cheon and Jun gave an early polynomial-time linear-algebraic attack on the braid Diffie–Hellman conjugacy problem [4]. Shpilrain and Ushakov emphasized more generally that solving the nominal conjugacy search problem is neither necessary nor sufficient for attacking certain group-based protocols [19]. Tsaban developed the linear-centralizer method and obtained polynomial-time cryptanalysis of several noncommutative key-exchange problems [21]. The linear-decomposition attack of Myasnikov and Roman’kov made the coefficient transfer principle explicit: once a target public element is represented in a known linear span, the same coefficients can be used to reconstruct the corresponding secret-dependent value without recovering the secret action [12]. Roman’kov subsequently applied linear decomposition to semidirect-product protocols [15] and to generic two-sided multiplication constructions [16]. Ben-Zvi, Kalka, and Tsaban broadened this perspective through cryptanalysis via algebraic spans [3]. Random sampling within this paradigm is also not new. Roman’kov showed in the cryptanalysis of the Modified Matrix Modular Cryptosystem that random public elements can probabilistically replace an explicitly constructed basis [17]. Our contribution is therefore not random spanning or coefficient transfer themselves. We instead consider the distribution actually induced by public protocol sampling, make no uniformity or anti-concentration assumption, and ask whether a finite sampled span covers an independently generated future target. This changes the objective from exact recovery of the full relevant span to distributional coverage of future cryptographic states. Related linear-algebraic attacks have continued to appear for modern semidirect-product and matrix-action proposals. For example, MAKE was rapidly shown to admit efficient cryptanalysis [11], and Battarbee, Kahrobaei, and Shahandashti established conditions under which semidirect-product key exchange over matrices with

noncommutative coefficient rings remains vulnerable to linearalgebraic methods [2]. These works further illustrate the recurring danger of hidden algebraic operations whose effects remain accessible through low-dimensional linear representations. Twisted and skew group-ring constructions. Our concrete application belongs to a recent family of public-key constructions based on twisted or skew dihedral group rings. de la Cruz and VillanuevaPolanco proposed key exchange, probabilistic encryption, and a KEM over twisted dihedral group algebras [7]; a related construction using skew dihedral group rings was subsequently proposed by de la Cruz, Martínez-Moro, and Villanueva-Polanco [6]. Tinani gave a polynomial-time cryptanalysis of the earlier twisted-dihedral construction through an algebraic reduction to equations over the underlying finite field [20]. More recently, Otero Sanchez studied generic attacks on protocols based on two-sided multiplication and analyzed several related group-ring constructions [14]. The 2024 construction combines twisting with skewing and may be nonassociative for its proposed parameters [5]. Consequently, some earlier generic theorems for two-sided multiplication do not apply verbatim. Classical basis-based decomposition methods may nevertheless be adaptable, so we do not claim that sampler-only access is necessary. To the best of our knowledge, prior work does not give an explicit attack on the CTSP or on Algorithms 6–8 of this exact 2024 PKE. Our attack uses only honest public sampling and evaluation and provides a distribution-free finite-sample guarantee with CTSP, plaintext-recovery, and IND–CPA consequences. Statistical learning of spans and subspaces. The statistical component of our analysis is related to learning linear structure from samples. Rudi, Cañas, and Rosasco studied the sample complexity of subspace learning, including PCA and spectral support estimation, under spectral assumptions on the data distribution [18]. Stable sample compression provides a different route to distributionfree generalization: Hanneke and Kontorovich established sharp data-dependent generalization guarantees for stable compression schemes [8], which we use to certify future coverage of the sampled span. Recent work has moved even closer to our statistical object. Noivirt, Sorrell, and Tsfadia use a procedure that outputs a subspace covering most of an arbitrary distribution as a building block for replicable learning [13], while Ye, Amin, and Özdağlar obtain distribution-free guarantees for cumulative acquisition of decision-relevant directions [22]. These learning results do not address cryptanalytic paired observations of the form (𝑋, 𝐴𝑋 ), coefficient transfer through an unknown secret map, or formal PKE security. Conversely, classical linear-decomposition attacks do not provide a distribution-free finite-sample characterization of how a sampled span covers future encryption randomness. Our work lies at this intersection, converting distributional span coverage into exact key-transport recovery and formal cryptographic insecurity.

8

Conclusion

This work develops a distributional view of linear-decomposition cryptanalysis. Rather than assuming that an adversary is given explicit algebraic generators or can reconstruct the entire relevant action space, we ask what can be learned using only the public

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

sampling-and-evaluation interface available to an honest participant. The resulting viewpoint shifts the cryptanalytic objective from recovering the full algebraic span to covering the probability mass of future ciphertexts. Our analysis shows that this distinction is fundamental. A finite collection of public samples can already provide strong guarantees for independently generated future targets under an arbitrary encryption-induced distribution. We characterize the optimal sample complexity of this sampled-span problem and combine the resulting coverage guarantees with the classical coefficient-transfer principle. This yields a generic cryptographic consequence: publicly samplable exact linear key transport of polynomial effective dimension cannot provide IND–CPA security when the transported value determines the decryption-critical payload. We demonstrate this phenomenon on the 2024 twisted–skew group-ring PKE. Despite the generally non-associative multiplication of the underlying construction, its correctness relation induces a fixed linear transport when the multiplication order is kept unchanged. Publicly generated protocol samples therefore suffice to attack the Computational Twisted–Skew Problem underlying the construction, leading directly to plaintext recovery and an IND– CPA break. Our experiments confirm the exact transport identity and the resulting end-to-end attack, while also illustrating the gap between algebraic rank recovery and probability-mass coverage under non-uniform sampling. The broader lesson is that hiding generators or making recovery of the complete orbit space difficult does not by itself prevent linear-decomposition cryptanalysis. For public-key constructions exposing exact linear key transport, the relevant security question is not only whether the secret action can be recovered, but whether its effect on future ciphertexts can be interpolated from publicly generated examples. Avoiding this attack therefore requires breaking one of the structural ingredients enabling such interpolation, rather than merely changing the sampling distribution or withholding an explicit algebraic basis. Understanding whether analogous attacks remain possible under noisy, approximate, or randomnessdependent transport is a natural direction for future work.

References [1] Iris Anshel, Michael Anshel, and Dorian Goldfeld. 1999. An Algebraic Method for Public-Key Cryptography. Mathematical Research Letters 6, 3–4 (1999), 287–291. doi:10.4310/MRL.1999.v6.n3.a3 [2] Christopher Battarbee, Delaram Kahrobaei, and Siamak F. Shahandashti. 2022. Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over NonCommutative Rings. Mathematical Cryptology 1, 2 (2022), 2–9. [3] Adi Ben-Zvi, Arkadius Kalka, and Boaz Tsaban. 2018. Cryptanalysis via Algebraic Spans. In Advances in Cryptology – CRYPTO 2018 (Lecture Notes in Computer Science, Vol. 10991). Springer, Cham, Switzerland, 255–274. doi:10.1007/978-3319-96884-1_9 [4] Jung Hee Cheon and Byungheup Jun. 2003. A Polynomial Time Algorithm for the Braid Diffie–Hellman Conjugacy Problem. In Advances in Cryptology – CRYPTO 2003 (Lecture Notes in Computer Science, Vol. 2729). Springer, Berlin, Heidelberg, 212–225. doi:10.1007/978-3-540-45146-4_13 [5] Javier de la Cruz, Edgar Martínez-Moro, Steven Muñoz-Ruiz, and Ricardo Villanueva-Polanco. 2024. Public Key Protocols from Twisted–Skew Group Rings. Cryptography 8, 3 (2024), 29. doi:10.3390/cryptography8030029 [6] Javier de la Cruz, Edgar Martínez-Moro, and Ricardo Villanueva-Polanco. 2022. Public Key Protocols over Skew Dihedral Group Rings. Mathematics 10, 18 (2022), 3343. doi:10.3390/math10183343 [7] Javier de la Cruz and Ricardo Villanueva-Polanco. 2024. Public Key Cryptography Based on Twisted Dihedral Group Algebras. Advances in Mathematics of Communications 18, 3 (2024), 857–877. doi:10.3934/amc.2022031 [8] Steve Hanneke and Aryeh Kontorovich. 2021. Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 132), Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.). PMLR, Brookline, MA, 697–721. [9] Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, and Choonsik Park. 2000. New Public-Key Cryptosystem Using Braid Groups. In Advances in Cryptology – CRYPTO 2000 (Lecture Notes in Computer Science, Vol. 1880). Springer, Berlin, Heidelberg, 166–183. doi:10.1007/3-540-44598-6_10 [10] Gérard Maze, Chris Monico, and Joachim Rosenthal. 2007. Public Key Cryptography Based on Semigroup Actions. Advances in Mathematics of Communications 1, 4 (2007), 489–507. doi:10.3934/amc.2007.1.489 [11] Chris Monico and Ayan Mahalanobis. 2020. A Remark on MAKE – a Matrix Action Key Exchange. arXiv:2012.00283 [cs.CR] [12] Alexei Myasnikov and Vitalii Roman’kov. 2015. A Linear Decomposition Attack. Groups, Complexity, Cryptology 7, 1 (2015), 81–94. doi:10.1515/gcc-2015-0007 [13] Moshe Noivirt, Jessica Sorrell, and Eliad Tsfadia. 2026. Computationally Efficient Replicable Learning of Parities and Applications. arXiv:2602.09499 [cs.LG] [14] Alvaro Otero Sanchez. 2025. On Key Exchange Protocol Based on Two-Side Multiplication Action. arXiv:2504.15880 [cs.CR] [15] Vitalii Roman’kov. 2015. Linear Decomposition Attack on Public Key Exchange Protocols Using Semidirect Products of (Semi)Groups. arXiv:1501.01152 [cs.CR] [16] Vitalii A. Roman’kov. 2017. A General Encryption Scheme Using Two-Sided Multiplications with Its Cryptanalysis. arXiv:1709.06282 [math.GR] [17] Vitalii A. Roman’kov. 2018. Cryptographic Analysis of the Modified Matrix Modular Cryptosystem. Herald of Omsk University 23, 4 (2018), 44–50. doi:10. 25513/1812-3996.2018.23(4).44-50 [18] Alessandro Rudi, Guillermo D. Cañas, and Lorenzo Rosasco. 2013. On the Sample Complexity of Subspace Learning. In Advances in Neural Information Processing Systems 26. Curran Associates, Inc., Red Hook, NY, 2067–2075. [19] Vladimir Shpilrain and Alexander Ushakov. 2006. The Conjugacy Search Problem in Public Key Cryptography: Unnecessary and Insufficient. Applicable Algebra in Engineering, Communication and Computing 17, 3–4 (2006), 285–289. doi:10. 1007/s00200-006-0009-6 [20] Simran Tinani. 2024. Cryptanalysis of a System Based on Twisted Dihedral Group Algebras. Transactions on Mathematical Cryptology 4, 1 (2024), 23–35. https://journals.flvc.org/mathcryptology/article/view/132262 [21] Boaz Tsaban. 2015. Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography. Journal of Cryptology 28, 3 (2015), 601–622. doi:10.1007/s00145-013-9170-9 [22] Yuhan Ye, Saurabh Amin, and Asuman Özdağlar. 2026. Learning DecisionSufficient Representations for Linear Optimization. In Proceedings of Thirty Ninth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 336), Steve Hanneke and Tor Lattimore (Eds.). PMLR, Brookline, MA, 6924– 6975. https://proceedings.mlr.press/v336/ye26a.html

A

Open Science

An anonymized research artifact supporting the experimental claims in Section 5 accompanies the submission. The archival repository is available at https://anonymous.4open.science/r/Distributionfree-LDA-5DF3/. The artifact contains our self-contained Python

Chen and Zhou

C.2

Proof of the One-Shot Sampled-Span Proposition

implementation of the twisted–skew arithmetic, the concrete PKE, and the sampler-only coefficient-transfer attack; the scripts for all four experimental stages; the raw and aggregated CSV and JSON outputs; and the visualization script and generated figures. The implementation performs field, ring, rank, span-membership, transport, and plaintext-recovery computations exactly over the stated finite fields. The experiment scripts use the Python standard library, while figure generation additionally uses Matplotlib. No external dataset, network service, proprietary software, or numerical linear-algebra tolerance is required. For reproducibility, the artifact records the master seed and deterministically derived setup and repetition seeds, together with the parameter sets, sample budgets, numbers of public setups and learned spans, challenges per span, bootstrap confidence level, and number of bootstrap repetitions. The released tables include persetup and per-span results in addition to the aggregates reported in the paper, permitting the hierarchical confidence intervals and all four figures to be regenerated from the saved outputs. The moderate and strong non-uniform samplers in the artifact are explicitly marked as synthetic stress tests over valid protocol randomness; they are not presented as the native sampler of the 2024 construction. The artifact is intended to reproduce the algebraic validation and empirical results, not to replace the self-contained mathematical proofs in this paper. No human-subject or personal data are used.

we have

B

pointwise, and thus

This work presents dual-use cryptanalytic techniques. Our evaluation is restricted to a published research construction and locally generated keys, randomness, and ciphertexts; it does not target deployed systems, access third-party services, or use personal data. We provide the attack details and research artifact to enable independent validation and to inform the design of safer public-key encryption schemes. The implementation is intended for research and defensive evaluation. Applying these techniques beyond the construction studied here should require appropriate authorization and follow applicable responsible-disclosure practices.

C Proofs for Preliminaries and Attack Setup C.1 Proof of the Coefficient-Transfer Lemma 𝑚 ∑︁

! 𝛼 𝑖 𝑋𝑖 =

𝑖=1

𝑚 ∑︁

𝐼 𝑗 := 1{𝑋 𝑗 ∉ 𝑆 𝑗 −1 }, 𝑞 𝑗 := E[𝐼 𝑗 ]. Every event 𝐼 𝑗 = 1 increases the dimension of the running span by exactly one. Hence 𝑚+1 ∑︁

𝐼 𝑗 = dim 𝑆𝑚+1 ≤ 𝑟 𝜇 ,

𝑗=1

and therefore 𝑚+1 ∑︁

𝑞 𝑗 ≤ 𝑟𝜇 .

𝑌★ =

(18)

𝑗=1

We next observe that (𝑞 𝑗 ) is non-increasing. Conditional on 𝑆 𝑗 −1 , independence of 𝑋 𝑗 gives Pr[𝑋 𝑗 ∉ 𝑆 𝑗 −1 | 𝑆 𝑗 −1 ] = 1 − 𝜇 (𝑆 𝑗 −1 ), therefore   𝑞 𝑗 = E 1 − 𝜇 (𝑆 𝑗 −1 ) . Since 𝑆 𝑗 −1 ⊆ 𝑆 𝑗 ,

𝑞 𝑗+1 ≤ 𝑞 𝑗 . It follows from (18) that 𝑞𝑚+1 ≤

𝑚+1 𝑟𝜇 1 ∑︁ 𝑞𝑗 ≤ . 𝑚 + 1 𝑗=1 𝑚+1

Finally, 𝑞𝑚+1 = Pr[𝑋 ★ ∉ span(𝑋 1, . . . , 𝑋𝑚 )], which proves (4). Whenever 𝑋 ★ ∈ 𝑊𝑚 , Gaussian elimination yields coefficients 𝛼𝑖 such that ∑︁ 𝑋★ = 𝛼 𝑖 𝑋𝑖 . 𝑖

Lemma 2.1 then recovers ∑︁

𝛼𝑖 𝑌𝑖 .

𝑖

□

𝛼𝑖 𝐴𝑋𝑖 .

𝑖=1

D Proofs for the Main Results D.1 Proof of the Distribution-Free Sampler-Only Certificate

Since 𝑌𝑖 = 𝐴𝑋𝑖 for every 𝑖, 𝑚 ∑︁

𝑆 0 := {0}.

Let

𝑌★ =

Proof. By linearity of 𝐴,

𝛼𝑖 𝑌𝑖 ,

𝑖=1

which proves (3). In the commuting-action specialization, 𝑋𝑖 = 𝐵 𝜌𝑖 𝑣,

𝑆 𝑗 := span(𝑋 1, . . . , 𝑋 𝑗 ),

1 − 𝜇 (𝑆 𝑗 ) ≤ 1 − 𝜇 (𝑆 𝑗 −1 )

Ethical Considerations

𝑌 ★ = 𝐴𝑋 ★ = 𝐴

Proof. For convenience, write 𝑋𝑚+1 := 𝑋 ★ and define

𝑌𝑖 = 𝐵 𝜌𝑖 𝑤,

𝑤 = 𝐴𝑣,

and 𝐴𝐵 𝜌𝑖 = 𝐵 𝜌𝑖 𝐴 implies 𝑌𝑖 = 𝐵 𝜌𝑖 𝐴𝑣 = 𝐴𝐵 𝜌𝑖 𝑣 = 𝐴𝑋𝑖 . This is precisely the coefficient-transfer mechanism used in classical linear decomposition attacks [12]; the present formulation isolates the linear relation needed later without requiring an explicit generating set for the action family. □

Proof. We reduce the sampled-span procedure to a realizable stable sample compression scheme and then apply Corollary 11 of Hanneke and Kontorovich [8]. Take the instance space to be 𝑉 and assign every training vector the same label 0. For any finite set 𝐾 ⊆ 𝑉 , define the reconstructed classifier ℎ𝐾 (𝑥) := 1 {𝑥 ∉ span(𝐾)} .

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

The compression map 𝜅 retains a basis of the sample span as described above, and the reconstruction map returns ℎ𝜅 (𝑆𝑚 ) . First, the scheme is sample-consistent. Indeed, 𝑋𝑖 ∈ span(𝜅 (𝑆𝑚 )) = 𝑊𝑚 for every 𝑖, so ℎ𝜅 (𝑆𝑚 ) (𝑋𝑖 ) = 0. Thus the empirical classification error is zero. Second, the compression scheme is stable. Suppose 𝜅 (𝑆𝑚 ) ⊆ 𝑆 ′ ⊆ 𝑆𝑚 . Since 𝜅 (𝑆𝑚 ) already spans 𝑆𝑚 , span(𝑆 ′ ) = span(𝑆𝑚 ). The compression rule applied to 𝑆 ′ returns some basis of span(𝑆 ′ ), and hence span(𝜅 (𝑆 ′ )) = span(𝜅 (𝑆𝑚 )). Therefore the reconstructed classifiers agree: ℎ𝜅 (𝑆 ′ ) = ℎ𝜅 (𝑆𝑚 ) . This is precisely the stability property required by stable sample compression. Finally, by (5), |𝜅 (𝑆𝑚 )| = b 𝑟𝑚 . Corollary 11 of Hanneke and Kontorovich [8] states that for any realizable stable compression scheme, with probability at least 1 − 𝛿, 4  𝑒 𝑅≤ 6|𝜅 (𝑆𝑚 )| + ln . 𝑚 𝛿 For our classifier,

The vector 𝑒 1 is the common type, while 𝑒 2, . . . , 𝑒𝑟 are 𝑘 rare, linearly independent types. Let 𝑁 rare denote the number of rare draws among the 𝑚 training samples. Then E[𝑁 rare ] = 2𝜀𝑚. 𝑘 If 𝑚 ≤ 8𝜀 , then 𝑘 E[𝑁 rare ] ≤ . 4 By Markov’s inequality,   𝑘 1 Pr 𝑁 rare ≥ ≤ . 2 2 Hence with probability at least 1/2, 𝑘 . 2 On this event, strictly more than half of the rare basis vectors have never appeared. Because these vectors are linearly independent, none of the unseen rare vectors lies in the span of the observed samples. Therefore 𝑘 2𝜀 𝑅 𝜇 (𝑊𝑚 ) > = 𝜀. 2 𝑘 Thus 1 Pr[𝑅 𝜇 (𝑊𝑚 ) > 𝜀] ≥ . 2 Since 𝛿 < 1/2, no distribution-free guarantee at confidence 1 − 𝛿 is possible when 𝑚 ≤ (𝑟 − 1)/(8𝜀), proving (9). Confidence-dependent lower bound. Now consider a two-dimensional distribution 𝑁 rare <

𝑅 = Pr [𝑋 ∉ 𝑊𝑚 ] = 𝑅 𝜇 (𝑊𝑚 ).

Pr[𝑋 = 𝑒 1 ] = 1 − 2𝜀,

𝑋 ∼𝜇

Substituting |𝜅 (𝑆𝑚 )| = b 𝑟𝑚 yields (6). The inequality b 𝑟𝑚 ≤ 𝑟 𝜇 immediately gives (7). For any fresh 𝑋 ★ ∈ 𝑊𝑚 , Lemma 2.1 recovers the corresponding 𝑌 ★, completing the cryptanalytic interpretation. □

D.2

Proof of the Optimal Sample-Complexity Theorem

Proof. Upper bound. By Theorem 3.1, with probability at least 1 − 𝛿, 𝑒 4  𝑅 𝜇 (𝑊𝑚 ) ≤ 6𝑟 + ln 𝑚 𝛿 for every distribution whose sampled orbit dimension is at most 𝑟 . Thus (8) is sufficient to ensure

If the rare vector 𝑒 2 does not appear among the 𝑚 samples, then 𝑊𝑚 = span(𝑒 1 ) and therefore 𝑅 𝜇 (𝑊𝑚 ) = 2𝜀 > 𝜀. The probability of this event is (1 − 2𝜀)𝑚 . For 𝜀 ≤ 1/4, ln(1 − 2𝜀) ≥ −

Pr[𝑋 = 𝑒 1 ] = 1 − 2𝜀, and Pr[𝑋 = 𝑒𝑖 ] =

2𝜀 , 𝑘

𝑖 = 2, . . . , 𝑟 .

2𝜀 ≥ −4𝜀, 1 − 2𝜀

so (1 − 2𝜀)𝑚 ≥ 𝑒 −4𝜀𝑚 . Consequently, if 𝑚<

𝑅 𝜇 (𝑊𝑚 ) ≤ 𝜀. Dimension-dependent lower bound. The argument follows the classical rare-types construction used in sample-compression lower bounds; a recent structurally analogous use appears in [22]. Work in 𝑉 = F𝑟 with linearly independent vectors 𝑒 1, . . . , 𝑒𝑟 . Let 𝑘 = 𝑟 − 1 and define

Pr[𝑋 = 𝑒 2 ] = 2𝜀.

ln(1/𝛿) , 4𝜀

then Pr[𝑅 𝜇 (𝑊𝑚 ) > 𝜀] > 𝛿. This proves (10). Combining (8), (9), and (10), and using 𝑎 +𝑏 max{𝑎, 𝑏} ≥ , 2 gives   𝑟 + ln(1/𝛿) 𝑚★span (𝑟, 𝜀, 𝛿) = Θ . 𝜀 □

Chen and Zhou

D.3

Proof of the IND-CPA No-Go Theorem for Recoverable Payloads

Proof. Fix a public key 𝑝𝑘. Before receiving the IND-CPA challenge, the adversary samples 𝑚 := 2𝑅(𝜆) − 1 independent values i.i.d.

𝜌 1, . . . , 𝜌𝑚 ← D𝑝𝑘 . Because the paired sampler is public, the adversary computes (𝑋𝑖 , 𝑌𝑖 ) = Pair(𝑝𝑘; 𝜌𝑖 ). By (11),

Under the convention 1 , 2 the adversary therefore has advantage at least 1 − 𝜈 (𝜆). 4 Finally, the adversary uses only 𝑂 (𝑅(𝜆)) public paired samples and polynomial-time linear algebra. Since 𝑅(𝜆) is polynomially bounded, the adversary is PPT. Since 𝜈 is negligible, the advantage remains non-negligible, and the scheme cannot satisfy IND-CPA security. If payload recovery is perfectly correct, then 𝜈 = 0 and the advantage is at least 1/4. □ AdvIND-CPA := Pr[𝑏 ′ = 𝑏] −

𝑌𝑖 = 𝐴𝑠𝑘 𝑋𝑖 . The adversary submits any two distinct equal-length messages 𝑚 0, 𝑚 1 . Let the challenge ciphertext be     ★ ★ 𝐶 ★ = 𝑋 ★, 𝐶 payload = 𝑋 𝜌 ★ , 𝐶 payload ,

E Proofs for the Twisted–Skew Application E.1 Proof of the Twisted–Skew Linear-Transport Lemma

where

Proof. Write elements of R as formal sums over 𝐺. By the defining product of the twisted–skew group ring [5], homogeneous terms satisfy

★

★

𝑌 = 𝑌𝜌 ★ = 𝐴𝑠𝑘 𝑋 . The adversary performs Gaussian elimination to test whether

(𝑢𝑔)(𝑣ℎ) = 𝑢 𝜃 𝜎 (𝑔)(𝑣) 𝛼 𝜆 (𝑔, ℎ) 𝑔ℎ,

(19)

𝑋 ★ ∈ span(𝑋 1, . . . , 𝑋𝑚 ). If so, it computes coefficients 𝛼 1, . . . , 𝛼𝑚 satisfying 𝑚 ∑︁ 𝑋★ = 𝛼 𝑖 𝑋𝑖 .

and the product of arbitrary sums is obtained by distributive extension. Each 𝜃 𝜎 (𝑔) is either the identity on F𝑞 2 or its 𝑞-Frobenius automorphism. Hence it fixes every scalar 𝑐 ∈ F𝑞 , so 𝜃 𝜎 (𝑔)(𝑐𝑣) = 𝑐𝜃 𝜎 (𝑔)(𝑣).

𝑖=1

Lemma 2.1 gives the exact transported value 𝑚 ∑︁ 𝑌★ = 𝛼𝑖 𝑌𝑖 . 𝑖=1

The adversary then runs the public recovery algorithm to obtain   ★ 𝑚 e = RecoverPayload 𝑝𝑘, 𝐶 payload , 𝑌★ . If 𝑚 e = 𝑚 0 , it outputs 0; if 𝑚 e = 𝑚 1 , it outputs 1; otherwise it outputs an independent uniform bit. If 𝑋 ★ does not lie in the sampled span, it also outputs an independent uniform bit. By Proposition 2.2,   𝑝 span := Pr 𝑋 ★ ∈ span(𝑋 1, . . . , 𝑋𝑚 ) 𝑟 (𝑝𝑘) 𝑚+1 𝑅(𝜆) 1 ≥1− = . 2𝑅(𝜆) 2 Let S denote the sampled-span event above, and let E denote the event that (13) correctly recovers the challenge message. The recoverable-payload condition gives ≥1−

Pr[¬E] ≤ 𝜈 (𝜆). On S ∩ E the adversary determines 𝑏 with certainty, while on ¬S it succeeds with probability 1/2. Therefore 1 Pr[𝑏 ′ = 𝑏] ≥ Pr[S ∩ E] + Pr[¬S] 2 1 ≥ 𝑝 span − 𝜈 (𝜆) + (1 − 𝑝 span ) 2 3 ≥ − 𝜈 (𝜆). 4

It follows directly from (19) that multiplication is additive in both inputs and F𝑞 -linear in each input separately. This assertion does not require associativity. With the parentheses kept fixed, let 𝐿𝑎1 (𝑥) := 𝑎 1𝑥,

𝑅𝛾b1 (𝑧) := 𝑧𝛾b1 .

Both maps are therefore F𝑞 -linear, and Ask = 𝑅𝛾b1 ◦ 𝐿𝑎1 . Explicitly, for 𝑥, 𝑦 ∈ R and 𝑐 ∈ F𝑞 ,
Ask (𝑥 + 𝑦) = 𝑎 1 (𝑥 + 𝑦) 𝛾b1
= 𝑎 1𝑥 + 𝑎 1𝑦 𝛾b1 = (𝑎 1𝑥)𝛾b1 + (𝑎 1𝑦)𝛾b1, and
Ask (𝑐𝑥) = 𝑎 1 (𝑐𝑥) 𝛾b1
= 𝑐 (𝑎 1𝑥) 𝛾b1
= 𝑐 (𝑎 1𝑥)𝛾b1 . Thus Ask is F𝑞 -linear. Finally, substituting 𝑐 1 = 𝑋 𝜌 into the verified correctness identity (14) gives Ask (𝑋 𝜌 ) = (𝑎 1𝑋 𝜌 )𝛾b1 = (𝑎 2 pk)𝛾b2 = 𝑌𝜌 . No product has been reassociated in this argument.

□

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

E.2

Proof of the CTSP Corollary

Proof. Fix the first CTSP public key 𝑝𝑘 1 = 𝜓 ((𝑎 1, 𝛾 1 ), ℎ) and its associated secret linear map A𝑝𝑘1 (𝑥) = (𝑎 1𝑥)𝛾b1 . Algorithm 2 of the original construction samples (𝑎 2, 𝛾 2 ) ← SK independently and sets 𝑝𝑘 2 = 𝜓 ((𝑎 2, 𝛾 2 ), ℎ),

𝑘 = 𝜓 ((𝑎 2, 𝛾b2 ), 𝑝𝑘 1 ).

Applying the correctness identity to these two key-generating pairs gives 𝑘 = (𝑎 2 𝑝𝑘 1 )𝛾b2 = (𝑎 1 𝑝𝑘 2 )𝛾b1 = A𝑝𝑘1 (𝑝𝑘 2 ). For each 𝑖 ∈ [𝑚], the adversary independently samples (𝑏𝑖 , 𝜂𝑖 ) ← SK and computes 𝑋𝑖 = (𝑏𝑖 ℎ)𝜂𝑖 ,

𝑌𝑖 = (𝑏𝑖 𝑝𝑘 1 )𝜂b𝑖 .

The same correctness identity, with (𝑎 2, 𝛾 2 ) = (𝑏𝑖 , 𝜂𝑖 ), gives 𝑌𝑖 = (𝑎 1𝑋𝑖 )𝛾b1 = A𝑝𝑘1 (𝑋𝑖 ). Conditioned on the fixed 𝑝𝑘 1 , the vectors 𝑋 1, . . . , 𝑋𝑚 , 𝑝𝑘 2 are i.i.d. from 𝜇𝑝𝑘1 . Therefore, Proposition 2.2 gives h i 𝑟 𝑝𝑘1 Pr 𝑝𝑘 2 ∈ spanF𝑞 (𝑋 1, . . . , 𝑋𝑚 ) ≥ 1 − . 𝑚+1 Whenever this event occurs, Gaussian elimination supplies coefficients 𝛼 1, . . . , 𝛼𝑚 ∈ F𝑞 such that 𝑚 ∑︁ 𝑝𝑘 2 = 𝛼 𝑖 𝑋𝑖 . 𝑖=1

Lemma 2.1 then recovers the CTSP target as 𝑚 ∑︁ b 𝑘 := 𝛼𝑖 𝑌𝑖 = A𝑝𝑘1 (𝑝𝑘 2 ) = 𝑘. 𝑖=1

This proves (16). Finally, R has one coefficient in F𝑞 2 for each element of 𝐺. If |𝐺 | = 2𝑛, then dimF𝑞 R = 2|𝐺 | = 4𝑛, so 𝑟 𝑝𝑘1 ≤ 4𝑛. Taking 𝑚 = 8𝑛 − 1 makes the lower bound at least 1/2. All samples and evaluations are public, and the remaining computation is polynomial-time Gaussian elimination. □

E.3

Proof of the Sampler-Only Break Corollary

Proof. Set 𝑝𝑘 1 = pk and identify the first component of the challenge with 𝑝𝑘 2 = 𝑋 ★. Its mask is the corresponding CTSP target 𝑌 ★ = Ask (𝑋 ★). For each independent public encryption of zero, the adversary obtains the CTSP training pair
(𝑋𝑖 , 𝑐 2,𝑖 ) = (𝑋𝑖 , 𝑌𝑖 ) = 𝑋𝑖 , Ask (𝑋𝑖 ) . Corollary 4.2 computes an estimate 𝑌b★ satisfying 𝑌b★ = 𝑌 ★ with ★ ★ probability at least 1−𝑟 pk /(𝑚+1). Since 𝑐 ★ 2 = 𝑚 +𝑌 , the adversary then recovers the plaintext exactly as b★ 𝑚★ = 𝑐 ★ 2 −𝑌 . This proves (17).

By definition, R has one coefficient in F𝑞 2 for each element of 𝐺. If |𝐺 | = 2𝑛, then dimF𝑞2 R = 2𝑛,

dimF𝑞 R = 4𝑛,

and hence 𝑟 pk ≤ 4𝑛. Taking 𝑚 = 8𝑛 − 1 gives 𝑟 pk 4𝑛 1 ≥1− = . 1− 𝑚+1 8𝑛 2 In the IND–CPA experiment, the adversary submits two distinct messages. On the sampled-span event it recovers the challenge plaintext and hence the challenge bit; otherwise it guesses uniformly. If the span-event probability is 𝑝 ≥ 1/2, then 1 1 𝑝 3 Pr[𝑏 ′ = 𝑏] ≥ 𝑝 + (1 − 𝑝) = + ≥ . 2 2 2 4 Its IND–CPA advantage is therefore at least 1/4. The attack uses only 8𝑛 − 1 public encryptions and polynomial-time linear algebra in the 4𝑛-dimensional F𝑞 representation. □

Related documents

• Beyond Explicit Generators: Distribution-Free Linear-Decomposition Attacks on Public-Key Encryption#659347
• Beyond Explicit Generators: Distribution-Free Linear-Decomposition Attacks on Public-Key Encryption#657211
• Fast correlation attacks through reconstruction of linear polynomials#378263
• Keyless secrecy against bounded adversaries#1000211
• Stabilizer-Public-Key Authentication: Partial Prediction Bounds and Limits of Key Reuse#1034851