- public-key matrix-multiplication trapdoor
- Updated Sun, 19 Jun 2022 19:33:27 GMT

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$

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