Stickel-type key exchange with hidden subspaces

Computer Science > Cryptography and Security [Submitted on 14 Jun 2026] Stickel-type key exchange with hidden subspaces Fintan Costello, Paul Watts 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). Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.16021 [cs.CR]   (or arXiv:2606.16021v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.16021 Focus to learn more Submission history From: Fintan Costello [view email] [v1] Sun, 14 Jun 2026 21:07:26 UTC (58 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)