5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Don Freecs
    Commented Jan 16, 2023 at 22:42
  • $\begingroup$ 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". $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Jan 16, 2023 at 22:52
  • $\begingroup$ 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 $\endgroup$
    – Don Freecs
    Commented Jan 16, 2023 at 23:27
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Jan 17, 2023 at 21:50
  • 1
    $\begingroup$ @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). $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Jan 19, 2023 at 1:02

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.