I'm arriving at a point in the construction of a cryptosystem, where I need to find a way to calculate matrix multiplication that is difficult to correctly invert.
Namely, given a $m$ by $n$ matrix $T = R \cdot S$, and the non-square $m$ by $n$ matrix $R$ where $S$ is an unknown $n$ by $n$ matrix, how many $S$ will be found assuming pseudoinverse can be easily found using logarithmic-time algorithms in the distant future?
Also, it is known that $S$ is of a known structure, $P \cdot D \cdot P^{-1}$ where $P$ is a random matrix and $D$ is a diagonal matrix, would this structure be exploitable?
Note that $T=RS$ is a system of $mn$ equations in $n^2$ unknowns. Assume that $m<n$ and $R$ has full rank $m$.Then its Moore-Penrose pseudo inverse is $R^+=R^*(RR^*)^{-1}$.
Moreover $S=R^+T+(I_n-R^+R)W$ where $W$ is any $n\times n$ matrix.
The general solution $S$ depends on $n^2-mn$ parameters, that is, you lose $mn$ unknowns amongst the entries of $S$. If a spy knows $k$ equalities of the form $T_i=R_iS$, then he knows $\approx kmn$ entries of $S$.
On the other hand, a random matrix $S$ has "always" the form $PDP^{-1}$.