Matrix Trapdoor AB+BA

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.

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$

Asked by user36960 (6,591 )
Sep 18, 2017 at 09:06