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

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.

• Which of the $S, A_i, C_i$ are unknowns? – poncho Aug 13 '20 at 11:59
• Sorry, only S is unknown. – yad50968 Aug 13 '20 at 12:54

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