2
$\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 $||e||_2 \leq \beta$.

Now assume $e_0$ is a solution to the ISIS instance $(q,A,b,\beta)$, so $A e_0 = b \mod q $ and $||e_0||_2 \leq \beta$. A clue to this solution is provided to me, so I receive $M e_0$, for a matrix $M \in \mathbb Z^{m\times m}_q$ of my choice. How could I choose $M$ in order to be able to retrieve $e_0$ from the clue $Me_0$, or more generally, to compute some short solution $e$ for $Ae = b$?

Solving ISIS on $(q,M,Me_0,\beta)$ doesn't help me, since that only finds a $e_1$ so that $Me_1=Me_0$, but not necessarily $Ae_1=b$ (and assuming I am able to solve that instance of ISIS...).

A possible solution, If I were able to solve ISIS, would be to solve $\begin{bmatrix}A\\ M\end{bmatrix}e = \begin{bmatrix}b\\ Me_0\end{bmatrix}$ , but if I could solve that... I could just solve $Ae=b$, right?

A trivial solution could be to choose $M = I$, so I receive $I e_0 = e_0$, which is a valid solution, since $Ae_0 = b$. However, in that case the clue would be "trivial", and I am interested in knowing other possible choices of $M$. Permutation matrices are also considered trivial (the identity is a particular case of permutation matrix).

My question is: What choices of $M$, different to permutation matrices, would enable me to calculate a solution to $Ae=b$, assuming I receive a clue $Me_0$?

$\endgroup$
  • 2
    $\begingroup$ What if $M$ is invertible (mod $q$)? $\endgroup$ – Chris Peikert Nov 30 '14 at 22:07
  • $\begingroup$ @ChrisPeikert: if $M$ could be invertible, then I don't understand your comment in a previous question. Does that mean that the ISIS problem is easy when the matrix is invertible (and the solution is guaranteed to exist)? $\endgroup$ – cygnusv Dec 1 '14 at 8:33
  • 4
    $\begingroup$ Yes, that's correct, because we can just left-multiply by the inverse matrix to recover the solution. $\endgroup$ – Chris Peikert Dec 2 '14 at 5:50
  • $\begingroup$ Thank you, @ChrisPeikert. I think your comment answers my question perfectly. Please, write an answer so I can accept it! $\endgroup$ – cygnusv Dec 2 '14 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.