ISIS problem in the case of $m=n$

Don Freecs

1/14/24, 12:46 PM

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

160

1 + 0

lattice-crypto

sis

Score:0

Crypto

Mark

1/16/24, 10:15 PM

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.

+ 6

Don Freecs

1/16/24, 10:42 PM

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

Mark

1/16/24, 10:52 PM

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

Don Freecs

1/16/24, 11:27 PM

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

Mark

1/17/24, 9:50 PM

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.

Don Freecs

1/18/24, 4:16 PM

yes $A^{-1}b$ will be a vector $t+s$ such that $s$ a short one with $As = 0 \mod q$ (I deduced this from the ISIS lattice). Me too I am unfamiliar with ISIS. for SIS clearly $A$ is not invertible since the short vector is not a zero vector.

Mark

1/19/24, 1:02 AM

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

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: ISIS problem in the case of $m=n$

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.