Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a cryptanalysis of Stickel-type key exchange schemes, revealing that all such schemes, including Stickel's original proposal and its extensions, can be compromised in polynomial time due to their reliance on public subspaces with specific commuting structures. The authors then introduce a novel key establishment scheme that obscures the commuting subspaces through conjugation by private terms, effectively thwarting the identified vulnerabilities. Notably, the witness-finding problem in this new scheme is shown to have a direct reduction from the NP-hard Edmonds' problem, suggesting a significant increase in security.
Stickel-type key exchange schemes can be broken in polynomial time, but a new approach hides vulnerabilities by using private terms to obscure key formation.
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).