Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Question

Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$.

Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$.

Here, $k \geq m>n$, and $q$ is a large prime.

And $S$ is unknown.

The following equations are satisfied

$SA_1 = C_1$
$SA_2 = C_2$
$\vdots$
$SA_k = C_k$

Can I solve this problem by using Gaussian elimination or any method of system of linear equations?

Note that I think this problem is similar with the lattice hard assumption - SIS.
I am not sure whether this problem has a solution.

Answer 1

Let $A' := [A_1 ~ | ~ \dots ~ | ~ A_k ] \in \mathbb{Z}_q^{m \times n k}$ and $C' := [C_1 ~ | ~ \dots ~ | ~ C_k ] \in \mathbb{Z}_q^{m \times n k}$. Then define $A \in Z_q^{m\times m}$ as the matrix whose columns are the first $m$ columns of $A'$. Likewise, define $C$ using the first $m$ columns of $C'$.

Then, $S$ satisfies $S \cdot A = C \pmod q$, thus, you can find it by computing $A^{-1}\cdot C \pmod q$.

---

Side note: why do you think that this problem is similar to the SIS problem? Notice that the SIS problem has a parameter $\beta$ that is an upper-bound to the norm of the accepted solutions and Gaussian elimination is likely to output solutions whose norm is above $\beta$ (thus, not valid solutions).