Matrix Trapdoor AB+BA

Question

I believe I'm probably not the first person to think of using this as a trapdoor.

Let $R$ be a square matrix ring, and $S$ a commutative subgroup of its multiplicative monoid.

Let $P \in R$ be a publicly-known matrix such that for all $x \in S$, $x$ can be constructed by calculating $x = P \cdot D \cdot P^{-1}$, where $D$ is some diagonal matrix ($D$ isn't necessarily in $S$, and $x$ isn't necessarily a diagonal matrix).

The trapdoor problem being: given $a \in S$ and $u = a \cdot b + b \cdot a$, find $b \in R$

What I don't know about is:

• How difficult is it to find $b$?

• What are some of the cases where finding $b$ would be easier than average?

My Guess:

• Because it's not possible to retrieve $b$ using ordinary matrix operations, some search is required.

• If $u = 0$, then $b = 0$ would be a trivial answer. If $u \in S$, then $b = (u \cdot a^{-1})/2$ would be another.

---

A bit of explanation on $S$: its elements are guaranteed to be commutative in multiplication because:

1) diagonal matrices are commutative in multiplication,

2) multiplying an element constructed as $a=P \cdot A \cdot P^{-1}$ with $b = P \cdot B \cdot P^{-1}$ where $A$ and $B$ are diagonal matrices yields $a\cdot b = P \cdot A \cdot P^{-1} \cdot P \cdot B \cdot P^{-1} = P \cdot A \cdot B \cdot P^{-1} = P \cdot B \cdot A \cdot P^{-1} = ... = b \cdot a$

Answer 1

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