arXiv CSopen access

Stickel-type key exchange with hidden subspaces

arXiv:2606.16021v1 [cs.CR] 14 Jun 2026

Stickel-type key exchange with hidden subspaces Fintan Costello School of Computer Science and Informatics, University College Dublin and Paul Watts Department of Physics, National University of Ireland Maynooth Abstract We give a witness-finding cryptanalysis of Stickel-type key exchange schemes, which involve two-sided multiplication of n × n matrices over Fp , where these matrices are drawn from public subspaces with a particular commuting structure. This analysis covers Stickel’s original proposal [1], Shpilrain’s polynomial extension of that scheme [2], Nager’s algebraic extension of that scheme [3], and more generally all Stickel-type approaches using public subspaces over matrix algebra in finite fields: all such schemes can be broken in polynomial time. We also describe a new key establishment scheme using two-sided matrix multiplication in which the commuting subspaces used to form the key are hidden via conjugation by private terms, blocking this specific public-subspace analysis; the witness-finding problem in this new scheme has a direct reduction from a standard NP-hard problem (Edmonds’ problem).

Traditional approaches to cryptographic key exchange are vulnerable to quantum attacks; given this, interest has grown in alternative key exchange mechanisms. One family of mechanism involves two-sided multiplication of elements from a public subgroup, subspace or ring over standard matrix algebra, originally proposed by Stickel [1] in terms of powers of invertible n×n

Stickel-style schemes 2

matrices over a finite field Fp . A range of key exchange schemes have been given using the general Stickel/two-sided-multiplication-by-public-subspaceelements approach; we describe various forms of this approach and give a tensor-based cryptanalysis that applies to all such schemes, at least over classical matrix algebra. We also describe a new hidden-subspace version of this approach, which removes the public linear structure used in this analysis. We begin with notation.

1

Notation

For some fixed prime p we take Mk = Mk (Fp ) to be the set of all k × k matrices with entries in Fp , and for some fixed dimension parameter n take M = Mn ; we assume that all matrices are members of M unless stated otherwise. For any set of matrices A we take A× to be the set of invertible matrices in A. For a matrix x we take Alg(x) to be the polynomial algebra in x; for a matrix x or set of matrices X we take Z(x) = {y | xy = yx},

Z(X ) = {y | xy = yx for all x ∈ X }

to be the set of matrices that commute with x or with all members of X . We also take Zk = Z(Mk ) = {λI | λ ∈ Fp } to represent the set of scalar matrices in Mk (the center of Mk ), and take Z = Zn . For matrices a, b, W we define a two-sided action operator ⊔ such that (a⊔b)(W ) = aW b For sets of matrices A, B we define A⊔B = {a⊔b | a ∈ A, b ∈ B} to be the set of all such operators generated by members of those sets; for matrix subspaces A, B we also define ( m ) X ⟨A⊔B⟩ = λi ui | ui ∈ A⊔B, m > 0, λi ∈ Fp i=1

Stickel-style schemes 3

to be the set of all linear combinations of operators u ∈ A⊔B. We take ⟨AW B⟩ = {u(W ) | u ∈ ⟨A⊔B⟩} to be the set of all matrices produced by applying these operators to W . → − Using the vectorisation operator X and the Kronecker or tensor product ⊗ we have − → −−→ (b⊤ ⊗ a) W = aW b (1) (a standard identity) and so −−−−−−→ − → (a⊔b)(W ) = (b⊤ ⊗ a) W and (a⊔b) and (b⊤ ⊗ a) are equivalent modulo reshaping of their inputs and outputs; since linear combinations are equivalent modulo matching reshaping of their terms, every operator u ∈ ⟨A⊔B⟩ has an equivalent matrix Fu (a sum of tensor products) such that −−−→ − → u(W ) = Fu W For matrix subspaces and operators such that u = (a⊔b) ∈ A⊔B,

v = (c⊔d) ∈ C ⊔D,

C ⊆ Z(A),

D ⊆ Z(B)

we have u(v(W )) = a(cW d)b = caW bd = c(aW b)d = v(u(W )) and so all such operators commute; since linear combinations of commuting operators will also commute, for such commuting subspaces all operators u ∈ ⟨A⊔B⟩,

v ∈ ⟨C ⊔D⟩

will also commute.

2

Stickel-type key exchange schemes

Stickel’s original scheme [1] begins with an initialisation stage, where Alice and Bob agree public non-commuting and invertible matrices A, B and W (the generators for the scheme). Given these generators, to construct a shared

Stickel-style schemes 4

key K Alice and Bob then exchange matrices as follows. Alice picks random integers f and g, sets a = Af and b = B g and publishes the matrix U = aW b while Bob similarly picks random integers ℓ and m, sets c = Aℓ and d = B m , and publishes V = cW d Given V Alice takes aV b = acW db = acW bd and given U Bob takes cU d = caW bd = acW bd (since powers of a given matrix commute) and Alice and Bob have a shared key K = acW bd. In our notation this corresponds to defining A, C to be the sets of all powers of A and defining B, D to be the sets of all powers of B; then Alice and Bob pick u ∈ A⊔B,

v ∈ C ⊔D

U = u(W ),

V = v(W )

and publish and since these operator sets commute they have u(V ) = u(v(W )) = v(u(W )) = v(U ) = K Note that the structure of this scheme means that the shared key K is a function only of the public transcript W, A, B, U, V only: there may be multiple private operators u, µ ∈ A⊔B,

v, ν ∈ C ⊔D

µ(W ) = U,

v(W ) = V,

such that u(W ) = U,

ν(W ) = V

(that is, multiple private choices for powers of A and B that produce the same public terms U and V : multiple ‘witnesses’ for the transcript) but since these operators all commute by construction, for each possible pairing of private choices u(W ) = µ(W ) = U and v(W ) = ν(W ) = V we get u(V ) = µ(V ) = v(U ) = ν(U ) = K and the shared key is a function of the public transcript W, A, B, U, V only.

Stickel-style schemes 5

2.1

Shpilrain’s extension

Stickel’s scheme was cryptanalysed by Shpilrain [4], who noticed that to get the shared key, an eavesdropper Eve needs only to find witness matrices ae and be such that ae ∈ Z(A),

be ∈ Z(B),

ae W be = U

(and these witnesses need not be powers of A and B). Given such witnesses Eve can then take ae V be = ae cW dbe = cae W be d = cU d giving the shared key. The advantage in this attack is that any matrices ae ∈ Z(A), be ∈ Z(B) that reproduce U will give the shared key; and if U is invertible then all that is needed is to find ae ∈ Z(A) and invertible xe ∈ Z(B) satisfying the linear equation ae W − U xe = 0 and taking be = x−1 e we have ae W be = U as required. To avoid this linear algebra attack, Shpilrain proposed a version using singular rather than invertible matrices A, B and using polynomials f, g, ℓ, m of A and B rather than powers [2]. Letting Alg(X) be the polynomial algebra generated by X, in Shpilrain’s scheme Alice has private matrices a ∈ Alg(A), b ∈ Alg(B) and Bob private matrices c ∈ Alg(A), d ∈ Alg(B), and Alice and Bob publish U = aW b,

V = cW d

Given V Alice takes aV b = acW db = acW bd (since polynomials of a given element commute) and given U Bob takes cU d = caW bd = acW bd getting a shared key K = acW bd as before. In our notation Shpilrain’s scheme is produced by defining A, C both equal to Alg(A) and B, D both equal to Alg(B), picking u ∈ A⊔B,

v ∈ C ⊔D

and running the scheme just as before; and since the operator structure of the scheme is unchanged, the shared key K is again a function of the public transcript.

Stickel-style schemes 6

2.2

Nager’s extension

We can also consider Nager’s [3] recent algebraic extension of Stickel’s approach. To construct a shared key in this scheme Alice picks random integers f, g, h, i and sets a1 = Af , b1 = B g , a2 = Ah and b2 = B i and publishes the matrix U = a1 W b1 + a2 W b2 while Bob similarly picks random integers j, k, ℓ, m, sets c1 = Aj , d1 = B k , c2 = Aℓ , d2 = B m , and publishes V = c1 W d1 + c2 W d2 Given V Alice takes a1 V b1 + a2 V b2 = a1 c1 W b1 d1 + a1 c2 W b1 d2 + a2 c1 W b2 d1 + a2 c2 W b2 d2 (the a and b terms commuting) and given U Bob takes c1 U d1 + c2 U d2 = a1 c1 W b1 d1 + a1 c2 W b1 d2 + a2 c1 W b2 d1 + a2 c2 W b2 d2 and Alice and Bob again have a shared key. In our notation this scheme is produced by defining A, C equal to Alg(A), B, D equal to Alg(B), picking operators from ⟨A⊔B⟩ and ⟨C ⊔D⟩ and running the scheme just as before (with, again, the shared key K being a function of the public transcript). There are also a range of key exchange approaches which use this Stickel or two-sided multiplication approach over tropical semirings rather than finite fields. Grigoriev and Shpilrain [5] gave the first such scheme, analogous to the Shpilrain polynomial scheme described above but using matrices over the tropical max-plus algebra; Kotov and Ushakov [6] gave a cryptanalysis of this scheme. A variety of other tropical Stickel-type schemes have been proposed, using matrices of various forms to construct a, c, b, d [for reviews of the tropical approach to cryptography, see 7, 8]. Since these differ from the above schemes in the choice of underlying representation rather than the key-exchange structure, we do not analyse them in detail.

2.3

A general form: commuting subspaces

We now describe a scheme that generalizes these different approaches. In the initialisation stage, Alice and Bob agree a public matrix W and public matrix

Stickel-style schemes 7

subspaces A, B, C, D such that C ⊆ Z(A), D ⊆ Z(B) (the generators for the scheme). To form a shared key, Alice picks some operator u ∈ ⟨A⊔B⟩ and publishes U = u(W ) while Bob picks some operator v ∈ ⟨C ⊔D⟩ and publishes V = v(W ) and since these operators commute they get their shared key by u(V ) = u(v(W )) = v(u(W )) = v(U ) = K This scheme includes the earlier schemes as special cases; and just as in those schemes, the shared key in this scheme is a function only of the public transcript W, A, B, C, D, U, V .

2.4

Cryptanalysis of Stickel-type schemes

Here we give a ‘witness-finding’ cryptanalysis for the general commuting subspace scheme described above. Alice and Bob’s operators u and v in this scheme can be expressed as u(X) =

m X

′

ai Xbi ,

v(X) =

m X

i=1

cj Xdj ,

ai ∈ A, bi ∈ B, cj ∈ C, dj ∈ D

j=1

Using the Kronecker identity (1) these operators have corresponding operator matrices Fu =

m X i=1

′

b⊤ i ⊗ ai ,

Gv =

m X

d⊤ j ⊗ cj ,

ai ∈ A, bi ∈ B, cj ∈ C, dj ∈ D

j=1

such that → − → − u(X) = Y ←→ Fu X = Y , and so

− → → − Fu W = U ,

→ − → − v(X) = Y ←→ Gv X = Y − → → − Gv W = V

Since all such operators u, v commute (by construction) the corresponding matrices necessarily also commute, giving → − − → − → → − → − Fu V = Fu Gv W = Gv Fu W = Gv U = K Letting A1 , . . . , Adim A ∈ A,

B1 , . . . , Bdim B ∈ B

Stickel-style schemes 8

be basis matrices for the public subspaces A and B then every tensor product b⊤ i ⊗ ai is a member of the linear subspace spanned by the set of basis tensors {Lij = Bv⊤ ⊗ Ai | 1 ≤ i ≤ dim A, 1 ≤ j ≤ dim B} and so the set of all possible admissible operator matrices F is the set of all matrices dim XA dim XB F (λ) = λij Lij i=1

j=1

for values of the coefficient matrix λ of dimensions (dim A)×(dim B); and every such matrix F (λ) will necessarily commute with the matrix Gv associated with Bob’s operator v. Eve can solve for λ in the linear matrix equation ! dim XA dim XB − → − → → − F (λ) W = λij Lij W = U i=1

j=1

→ − → − in polynomial time via standard matrix algebra, giving F (λ) V = K and recovering the shared key. Note that this tensor-based analysis is a generalisation of a similar recent result by Otero Sanchez [9], which gives a cryptanalysis of key exchange schemes using two-sided actions on a semiring (focusing in particular on tropical semirings and digital semirings).

3

Hidden commuting subspaces

The central problem with the above schemes is that the spaces used to construct Alice and Bob’s commuting operators u and v are public, and so these operators can be solved for linearly in terms of public tensor bases. Here we describe a two-sided multiplication scheme where these commuting spaces are not publicly available in linear form, but are instead hidden via conjugation (by ‘transport’). Where the above schemes had two stages (initialization and key exchange) this hidden subspace approach has three: initialization (where Alice and Bob agree a set of public generators), subspace construction (where they exchange information allowing them to form appropriately commuting hidden subspaces A, B, C, D), and key exchange (where they pick operators u ∈ ⟨A⊔B⟩ and v ∈ ⟨C ⊔D⟩ respectively, publish U = u(W ), V = v(W ), and get K = u(V ) = v(U ) as before).

Stickel-style schemes 9

For a given x and an invertible matrix r, we say that the conjugation rxr−1 is the operation of transporting the core matrix x by the transporter r; any matrix we refer to as a ‘transporter’ is implicitly invertible (and we typically take this as read). In this scheme we use the fact that for a core subspace X and a transporter subspace R, if Bob publishes a matrix à = rb xb rb−1 for rb ∈ Z(R)× , xb ∈ X and Alice publishes a matrix C̃ = ra xa ra−1 for ra ∈ R× , xa ∈ Z(X ) then taking r = ra rb = rb ra (since these transporters necessarily commute) Alice and Bob can form private matrices A = ra Ãra−1 = rxb r−1 ,

C = rb C̃rb−1 = rxa r−1

and since xa and xb commute we have AC = rxb xa r−1 = rxa xb r−1 = CA and these two private matrices commute; and thus the private subspaces A = Alg(A), C = Alg(C) also commute. Given this, our proposed scheme runs as follows: Initialisation: Alice and Bob agree a public invertible matrix W , two public core subspaces X , Y with centralizers Z(X ), Z(Y), and two transporter subspaces R, S with centralizers Z(R), Z(S) (where the transporter subspaces and their centralizers all contain invertible matrices). These are the generators for the scheme. Subspace construction: Given these generators Alice constructs two matrices C̃, D̃ such that × × C̃ = ra xa ra−1 , D̃ = sa ya s−1 a , ra ∈ R , xa ∈ Z(X ), sa ∈ Z(S) , ya ∈ Y

for randomly chosen private transporters ra , sa and private core matrices xa , ya ; she publishes C̃, D̃ as her public keys, and keeps ra , sa as her private keys. Similarly Bob constructs two matrices Ã, B̃ such that × × Ã = rb xb rb−1 , B̃ = sb yb s−1 b , rb ∈ Z(R) , xb ∈ X , sb ∈ S , yb ∈ Z(Y)

for randomly chosen private transporters rb , sb and private core matrices xb , yb , publishes Ã, B̃ as his public keys, and keeps rb , sb as his private keys.

Stickel-style schemes 10

Key exchange: Alice now forms private subspaces A = ra Alg(Ã) ra−1 ,

B = sa Alg(B̃) s−1 a

and Bob forms private subspaces C = rb Alg(C̃) rb−1 ,

D = sb Alg(D̃) s−1 b

and given the commuting structure of the core and transporter subspaces, we have C ⊆ Z(A), D ⊆ Z(B) as above. Now a general Stickel-type key exchange runs as before, but using these private commuting subspaces: Alice picks some operator u ∈ ⟨A⊔B⟩, Bob picks some operator v ∈ ⟨C ⊔D⟩, they publish U = u(W ), V = v(W ), Alice takes K = u(V ) = u(v(W )) and Bob takes v(U ) = v(u(W )) = K, and they have a shared key.

3.1

Correctness and transcript dependence

Assuming fixed generators we represent a given key exchange transcript in this scheme as τ = (Ã, B̃, C̃, D̃, U, V ) For fixed generators, Alice and Bob have some constrained set of choices for their core and transporter matrices (those choices that are consistent with the requirements of the scheme); for fixed τ we take ΩA (τ ) to be the set of honest choices (xa , ya , ra , sa , u) for Alice for which ra xa ra−1 = C̃,

sa ya s−1 a = D̃,

u(W ) = U,

u ∈ ⟨ra Alg(Ã)ra−1 ⊔ sa Alg(B̃)s−1 a ⟩

also hold (so ΩA (τ ) is the set of all honest choices that also reproduce Alice’s part of the transcript τ ). We similarly take ΩB (τ ) to be the set of all honest choices (xb , yb , rb , sb , v) for Bob for which rb xb rb−1 = Ã,

sb yb s−1 b = B̃,

v(W ) = V,

v ∈ ⟨rb Alg(C̃)rb−1 ⊔ sb Alg(D̃)s−1 b ⟩

also hold (so ΩB (τ ) is the set of all honest choices that also reproduce Bob’s part of τ ). Using this notation we have Proposition 1. For a fixed transcript τ generated in this hidden subspace scheme, all witness tuples in ΩA (τ ) × ΩB (τ ) yield the same shared key: the shared key is determined by τ .

Stickel-style schemes 11

Proof. From the construction of this scheme and the fact that these sets ΩA (τ ), ΩB (τ ) contain only choices that are honestly consistent with the scheme’s requirements and the transcript τ , we see that for any pair of tuples (xa , ya , ra , sa , u) ∈ ΩA (τ ),

(xb , yb , rb , sb , v) ∈ ΩB (τ )

we have u(v(W )) = v(u(W )) (the operators in these tuples necessarily commute). Given this, fix an operator u∗ for some tuple (xa , ya , ra , sa , u∗ ) ∈ ΩA (τ ); then we have u∗ (W ) = U for that operator (because this holds for all such operators), and can define a fixed value K = u∗ (V ). Then for any tuple in ΩB (τ ) the operator v in that tuple gives v(W ) = V (because this holds for all such operators) and v commutes with the fixed operator u∗ . This means we have v(U ) = v(u∗ (W )) = u∗ (v(W )) = u∗ (V ) = K; and so for any tuple in ΩB (τ ) the operator v gives v(U ) = K for this fixed value K. Since all pairs of operators u, v in these sets commute we have u(V ) = u(v(W )) = v(u(W )) = v(U ) = K for all such pairs, and for any tuple in ΩA (τ ) the operator u also gives u(V ) = K. Thus all honest and transcriptconsistent choices for Alice and Bob’s private terms necessarily give the same shared key K for that transcript: the shared key has a fixed value K fully determined by the transcript τ .

3.2

Parameter and subspace constructions

This scheme gives Alice and Bob a shared key K for all choices of prime p and matrix dimension n, all choices for the public matrix W and the public core subspaces X , Y with their centralizers Z(X ), Z(Y), and all choices for the transporter subspaces R, S and Z(R), Z(S) where each transporter subspace contains invertible matrices. For security we recommend large n and some prime p < n, and core subspaces chosen so that X , Z(X ), Y, Z(Y) are all nontrivial and at least dimension αn for some constant α. We recommend transporter subspaces chosen so that R× , Z(R)× , S × , Z(S)× are all nontrivial, do not commute with the core subspaces or with W , and so that all have dimensions of at least γn for some constant γ. We also recommend that the core and transporter spaces R, S, X , Y be subject to conjugation by independent randomly chosen invertible matrices θR , θS , θX and θY , so any block or tensor structure is not shared across these spaces. A simple block construction giving transporter spaces of dimensions approximately n2 /4 (so exceeding these requirements) is to take n = 2k, chose

Stickel-style schemes 12

some invertible matrix θR , and define    r 0 −1 R = θR θ , 0 z R so that

 Z(R) =

 r ∈ Mk , z ∈ Zk

  z 0 −1 θR θ , 0 r R

 r ∈ Mk , z ∈ Zk

and both R and Z(R) have dimensions k 2 + 1 ≈ n2 /4 and contain invertible matrices; a similar construction (with some conjugator θS ) gives S and Z(S) with the same dimensions. We don’t require this transporter subspace construction: we simply give it to show an extreme example.

4

Analysis

Just as in the various public subspace schemes described earlier, the shared key K in this hidden subspace scheme is a function of the public key-exchange transcript only. This transcript, however, by design does not include the subspaces A, B, C, D over which key exchange runs; and so our witness-finding cryptanalysis of public subspace key exchange in section 2.4 does not apply directly to this scheme. Instead, the natural path to key recovery here is one where an eavesdropper Eve identifies witness transporters that allow her to recover Alice or Bob’s hidden subspaces; then can she get the shared key K as in section 2.4. The witness-finding form of this approach matches Shpilrain’s attack on Stickel’s original scheme, and our cryptanalysis of generalized Stickel-type schemes; as far as we know, the same witness-finding pattern also covers all successful attacks on tropical Stickel-type variants: our heuristic security assumption is that key exchange in this scheme will be secure if it is secure against such a witness-finding attack. Here we give an initial analysis of the complexity of this witness-finding approach, showing that witness-finding key recovery is NP-hard in the worst case (via reduction to a standard problem). Note that we do not have any proof of hardness for the scheme in general: there may be approaches that avoid witness-finding entirely and recover the shared key some other way. To recover the shared key in this scheme via witness-finding, Eve solves for matrices x, y, ρ, σ such that ρ−1 C̃ρ = x,

x ∈ Z(X ), ρ ∈ R× ,

σ −1 D̃σ = y,

y ∈ Y, σ ∈ Z(S)×

Stickel-style schemes 13

and if she finds an operator µ such that µ(W ) = U,

µ ∈ ⟨Ae ⊔ Be ⟩ where Ae = ρAlg(Ã)ρ−1 , Be = σAlg(B̃)σ −1

then she has a set of witnesses (x, y, ρ, σ, µ) ∈ ΩA (τ ) and gets the shared key by taking µ(V ) = K. Given such transporters ρ, σ, solving for such an operator µ can be done via linear algebra over tensors as in section 2.4; and so the computational challenge for Eve is to solve the following problem: Problem 1: Restricted conjugacy into subspaces. Given a matrix Q, a subspace T , and a subspace Φ (all in M) return a matrix ρ such that ρ ∈ Φ× , ρ−1 Qρ = t for some t ∈ T or report failure if no such ρ exists. This is close to several well-studied orbit and matrix-space problems. If the target matrix t is fixed rather than ranging over the subspace T , Problem 1 reduces to a matrix-tuple conjugacy or transporter problem: given two fixed matrices Q, t, this asks for a transporter ρ such that ρ−1 Qρ = t, with recent work of Qiao and Sun providing polynomial-time canonical form solutions for matrix tuples over finite fields [10]. The extra features in our setting are that the target matrix t is not fixed but is an unknown member of the subspace T , and that the transporter ρ is itself restricted to lie in a specified subspace Φ. With these features we can show that Problem 1 has a reduction from the standard hardness problem Problem 2: Edmonds’ problem (search version) Given a subspace B ⊆ Mk , return a matrix b ∈ B × (an invertible member of B) or report failure if no such invertible member exists. We show this with a block construction that uses the same block-scalar transporter shape as the illustrative transporter spaces described above. Let

Stickel-style schemes 14

B ≤ Mk be an instance of Edmonds’ problem. Set n = 2k and define    ϕ 0 Φ= , ϕ ∈ M k , z ∈ Zk . 0 z Choose a random invertible matrix q ∈ M× k and random matrices Q11 , Q21 , Q22 ∈ Mk and set   Q11 q Q= Q21 Q22 and define the target subspace    T11 b TB = : T11 , T21 , T22 ∈ Mk , b ∈ B . T21 T22 (a linear subspace of Mn ) Now take   ϕ 0 ρ= ∈ Φ× , 0 z

× ϕ ∈ M× k , z ∈ Zk .

and we have  −1     −1  ϕ 0 Q11 q ϕ 0 ϕ Q11 ϕ ϕ−1 qz ρ Qρ = = −1 . 0 z −1 Q21 Q22 0 z z Q11 ϕ Q22 −1

and ρQρ−1 ∈ TB when ϕ−1 qz ∈ B (all other requirements for membership in TB being satisfied automatically). Since ϕ, q, z are invertible this means that any solution ρ to Problem 1 gives an invertible element b = ϕ−1 qz ∈ B × , and hence a solution to Problem 2. Conversely, suppose B contains an invertible element b ∈ B × (a solution to Problem 2). Taking z = I and ϕ = qb−1 gives ϕ ∈ M× k and

ϕ−1 qz = ϕ−1 q = b.

Thus any solution b to Problem 2 gives a transporter ρ such that  −1  qb 0 ρ= ∈ Φ× , ρ−1 Qρ ∈ TB . 0 I

Stickel-style schemes 15

and hence gives a solution to Problem 1. This means that every instance of Problem 2 can be solved by obtaining a solution to a corresponding instance of Problem 1; and so Problem 1 must be at least as hard as Problem 2. Problem 2 is known to be NP-hard in the matrix dimension k for fixed field Fp [11], though it does have polynomial time randomised solutions for p > 2k = n [12, 13], and so solving Problem 1 will be NP-hard in the worst case, at least when p < n; and this witness-finding approach to key recovery inherits this worst-case hardness.

5

Discussion

We’ve given a general cryptanalysis showing that Stickel-type key exchange schemes over public subspaces can be broken in polynomial time by linear algebra over tensor products of those subspaces, and given a new version of this type of scheme where the key-exchange subspaces are not public, blocking this attack. We have also shown that to recover the shared key in these schemes via witness-finding (the standard approach for Stickel-type schemes) in the worst case requires an eavesdropper Eve to solve an NPhard problem. This does not, of course, show that finding the shared key in this scheme is unconditionally NP-hard: there may be approaches that avoid witness-finding entirely and recover the shared key in polynomial time some other way. One possible drawback of the hidden subspaces approach described here is that it gives our eavesdropper Eve public subspaces containing all private core and transporter matrices used in the scheme (and so linear algebraic structure that can be used to express those private matrices). In a second paper we give a more complex version of this hidden subspace approach, where transporters are formed via local rather than global commutation so that, for example, Alice and Bob’s transporters ra and rb do not themselves commute but where rb ra x ra−1 rb−1 = ra rb x rb−1 ra−1 holds for all x ∈ X (the transporters commute locally at X ). Alice and Bob’s transporters are not members of public subspaces R, S (or their centralizers) in this ‘local commuting transporters’ scheme, but instead are solutions to public non-linear problems (versions of Problem 1). This means that no linear algebraic structure describing those transporters is available to Eve,

Stickel-style schemes 16

and getting the shared key by recovery of witness transporters ρa , σa becomes a more complex problem.

References [1] Eberhard Stickel. A new method for exchanging secret keys. In Third International Conference on Information Technology and Applications (ICITA’05), volume 2, pages 426–430. IEEE, 2005. [2] Vladimir Shpilrain and Alexander Ushakov. A new key exchange protocol based on the decomposition problem. arXiv preprint math/0512140, 2005. [3] Daniel Nager. Stickel’s key agreement algebraic variation. Cryptology ePrint Archive, Paper 2024/792, 2024. [4] Vladimir Shpilrain. Cryptanalysis of Stickel’s key exchange scheme. In International computer science symposium in Russia, pages 283–288. Springer, 2008. [5] Dima Grigoriev and Vladimir Shpilrain. Tropical cryptography. Communications in Algebra, 42(6):2624–2632, 2014. [6] Matvei Kotov and Alexander Ushakov. Analysis of a key exchange protocol based on tropical matrix algebra. Journal of Mathematical Cryptology, 12(3):137–141, 2018. [7] Steve Isaac and Delaram Kahrobaei. A closer look at the tropical cryptography. International Journal of Computer Mathematics: Computer Systems Theory, 6(2):137–142, 2021. [8] Kashif Ahmed, S Pal, and Radha Mohan. A review of the tropical approach in cryptography. Cryptologia, 47(1):63–87, 2023. [9] Alvaro Otero Sanchez. On key exchange protocol based on two-side multiplication action, 2025. [10] Youming Qiao and Xiaorui Sun. Canonical forms for matrix tuples in polynomial time. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS), 2024. Available as arXiv:2409.12457.

Stickel-style schemes 17

[11] Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit. The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences, 58(3):572–596, 1999. [12] László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565–574, 1979. [13] Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized wong sequences and their applications to edmonds’ problems. Journal of Computer and System Sciences, 81(7):1373–1386, 2015.