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

  • 2
    $\begingroup$ Which of the $S, A_i, C_i$ are unknowns? $\endgroup$
    – poncho
    Aug 13, 2020 at 11:59
  • $\begingroup$ Sorry, only S is unknown. $\endgroup$ Aug 13, 2020 at 12:54

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.