# ISIS problem in the case of $m=n$

The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $$q$$, a matrix $$A\in \mathbb{Z}^{n\times m}_q$$, a vector $$b\in \mathbb{Z}^{n}_q$$, and a real $$\beta$$, find an integer vector $$e\in\mathbb{Z}^m$$ such that $$Ae=b\mod q$$ and $$0<\Vert e\Vert_2\leq\beta$$.

if we assume that $$n=m$$ is this average-case problem is still hard for a well-chosen $$(n,q,\beta)$$?

because (I have tested many matrices and solved it) in that case a Gaussian Elimination can be performed given $$(A,b)$$.

Generally gaussian elimination is ruled out through choosing $$\beta$$ appropriately, as in general Gaussian elimination will find you a solution $$e'$$ such that $$Ae'\equiv b\bmod q$$, but this solution is generally not short. In particular $$\beta > \sqrt{n\log q}$$ suffices, and $$\beta\geq q$$ is trivial to find.

See for example this paper, though it is for SIS (rather than ISIS). I am under the (admittedly vague) impression that the problems have similar hardness.

• yeah in general is not short but if the rank of the matrix mod $q$ is $n$ then it is injective hence it will finds a short solution Jan 16 at 22:42
• I don't believe that reasoning holds. See Theorem 1.1. of the linked paper. In general $m$ tends to not matter for lattice problems that much, especially in the regime where $m = \Theta(n)$ (where you are). Note that larger $m$ can matter some for "combinatorial" attacks, but this tends to require the other parameters to be rather "extreme".
– Mark
Jan 16 at 22:52
• for $m=n$ in Vector Space theory, we could see $A$ as a Map from $V=GF(q) ^n$ to itself (i.e. endomorphism) since the dimension of $V$ is $n$ and with the knowledge of that $A$ has a $det(A)$ coprime with $q$ then $A$ is invertible modulo $q$ hence it is a bijection in particular $A$ will be injective Jan 16 at 23:27
• yes, but $A^{-1}b$ need not have small norm. Note that the norm is taken over $\mathbb{Z}$, so is separate from the $\mathbb{Z}_q$ arithmetic. That being said, I am less familiar with the ISIS problem. But for SIS this is not an issue, provided $\beta$ is chosen appropriately. As I imagine ISIS is only harder than SIS (it shouldn't be easier to find short vectors in an arbitrary coset of a lattice, rather than the lattice itself), I would imagine what I'm saying to still hold.
– Mark
Jan 17 at 21:50
• @DonFreecs $A^{-1}b =:w$ will be a potentially non-short vector. You're right that if you know some short element of the SIS latticee $s$, then any element of $t \pm \mathbb{Z} s$ would be a solution to the ISIS problem, and you can probably optimize over the choice of scalar $\mathbb{Z}$ to find a short solution. This required knowing short solution $s$ to the SIS problem though, which we both agree doesn't seem realistic (when appropriately parameterized).
– Mark
Jan 19 at 1:02