Matrix Trapdoor AB+BA
How difficult is it to find $b$?


If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps.

If $u$ is specified explicitly in the public key or the ciphertext or the signature, that'll take $O(n^2)$ space; in other words, to get $n$-bit security, you'll need to take $O(2^{n/3})$ space (field elements).

Currently, the lowest level of security we consider is $n=80$ bit (and that's for constrained devices that really can't do any more); even at that level, you'll end up with using multimegabyte public keys/ciphertext/signatures (at the very least, assuming that there's no better attack).

Now, if your cryptosystem has nice properties, for example, is at least partially homomorphic, it might be of some interest.  However, if it's just a simple public key encryption or signature system, well, something with a relatively low-exponent polytime solution doesn't look at all promising...