Stickel-type key exchange with hidden subspaces

• URL: http://arxiv.org/abs/2606.16021v1
• Date: Sun, 14 Jun 2026 21:07:26 GMT
• Title: Stickel-type key exchange with hidden subspaces
• Abstract summary: We give a witness-finding cryptanalysis of Stickel-type key schemes.<n>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 by private terms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a witness-finding cryptanalysis of Stickel-type key exchange schemes, which involve two-sided multiplication of $n \times n$ matrices over $\mathbb{F}_p$, where these matrices are drawn from public subspaces with a particular commuting structure. This analysis covers Stickel's original proposal , Shpilrain's polynomial extension of that scheme, Nager's algebraic extension of that scheme, 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).

Related papers

• Expressivity of congruence-based architectures for DNNs on positive-definite matrices [0.0]
  We focus on congruence-like layers, in which the input matrix is multiplied on the left and right by a (possibly rectangular) weight matrix $W$ and its transpose.<n>Such layers lie at the core of the celebrated SPDNet and have also been employed independently for dimensionality reduction on positive-definite data.<n>We show that the (semi)-orthogonality constraint commonly imposed on $W$ limits the expressivity of these layers.
  arXiv  Detail & Related papers  (2026-06-01T17:01:08Z)
• Generalized Reduction to the Isotropy for Flexible Equivariant Neural Fields [43.58107597764876]
  We show that, when a group $G$ acts transitively on a space $M$, any $G$-invariant function on a product space $X times M$ can be reduced to an invariant of the isotropy subgroup $H$ of $M$ acting on $X$ alone.<n>We apply this characterization to Equivariant Neural Fields, extending them to arbitrary group actions and homogeneous conditioning spaces.
  arXiv  Detail & Related papers  (2026-03-08T10:41:23Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Low-degree lower bounds via almost orthonormal bases [47.83594448785856]
  Low-degrees have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models.<n>In this work, we propose a more direct proof strategy.
  arXiv  Detail & Related papers  (2025-09-11T11:07:36Z)
• VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
  Lattice-based cryptography is a foundation for post-quantum security.<n>This work introduces Variety-LWE (VLWE), a new structured lattice problem based on algebraic geometry.<n>We prove VLWE's security by reducing it to multiple independent instances, demonstrating resilience against classical and quantum attacks.
  arXiv  Detail & Related papers  (2025-02-11T06:04:24Z)
• Irreducible matrix representations for the walled Brauer algebra [0.9374652839580183]
  This paper investigates the representation theory of the algebra of partially transposed permutation operators, $mathcalAd_p,p$.<n>It provides a matrix representation for the abstract walled Brauer algebra.<n>This algebra has recently gained significant attention due to its relevance in quantum information theory.
  arXiv  Detail & Related papers  (2025-01-22T18:22:20Z)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  Global Covariance Pooling (GCP) has been demonstrated to improve the performance of Deep Neural Networks (DNNs) by exploiting second-order statistics of high-level representations.<n>This paper provides a comprehensive and unified understanding of the matrix logarithm and power from a Riemannian geometry perspective.
  arXiv  Detail & Related papers  (2024-07-15T07:11:44Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Subsets of groups in public-key cryptography [0.46960837342692324]
  We present the subset version of two protocols introduced by Shpilrain and Ushakov with some examples in ascending HNN-extensions of free-abelian groups. We also introduce several new group theoretic problems arising from this work.
  arXiv  Detail & Related papers  (2023-11-25T14:35:36Z)
• Hypothesis testing on invariant subspaces of non-diagonalizable matrices with applications to network statistics [0.0]
  Wald tests for invariant vectors and $t$-tests for their individual coefficients perform well in simulations.<n>We find that statisticians only need control over the first-order Davis-Kahan bound to control convergence rates of invariant subspace estimators to higher-orders.
  arXiv  Detail & Related papers  (2023-03-31T17:48:20Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Towards a conjecture on a special class of matrices over commutative rings of characteristic 2 [0.1813006808606333]
  We prove the conjecture posed by Keller and Rosemarin at Eurocrypt 2021 on the nullity of a matrix of a block matrix with Hadamard type blocks. We also reveal the structure formed by Hadamard over commutative rings from the perspectives of group algebra and algebra.
  arXiv  Detail & Related papers  (2021-12-26T09:39:32Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)

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

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