Stickel-type key exchange with hidden subspaces (opens in new tab)

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 usi...