3
$\begingroup$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over a random choice of $\gamma$ and the $\xi_i$?

This is closely related to the SIS problem, but instead of having several equations this only involves one. Also, the question is not about the hardness of finding such solutions, but about the conditions on which at most one solution exists.

As an example, if $\ell = 2$, then the problems looks much like the Knapsack problem, and is likely to have one solution at most. However, as $\ell$ grows larger, the chances there are more than one solution also grow.

$\endgroup$
2
  • $\begingroup$ Is $p$ supposed to be prime? And when you say a solution you mean a non-zero vector $( x_1, ..., x_m)$, right? $\endgroup$ Dec 17 '18 at 8:03
  • $\begingroup$ Not necessarily non-zero, since $\gamma$ is chosen at random. And yes, $p$ is supposed to be a prime :) $\endgroup$
    – Daniel
    Dec 20 '18 at 23:00
2
$\begingroup$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$, where $\gamma$ and the $\xi_i$ are uniformly random?

For any $\ell \ge 2$, there will be values of $\gamma$ and $\xi_i$ for which there are multiple solutions; one such set of values would be $\gamma = 0$ and $\xi_1 = 0$. Hence, any condition that forbids multiple solutions would necessarily have $\ell < 2$ (which isn't very interesting)

Perhaps you mean to ask "yields more than one solution with probability $< \epsilon$"; that is a rather harder question, but might give you a more useful answer.

$\endgroup$
1
  • $\begingroup$ I'm sorry, you're definitely right, I mentioned that the parameters of the equation were chosen at random but never included this in the requirement. Indeed, what I meant is that with high probability over this choice the equation will have at most one solution (of course, this requires the parameter space to be large, but that's fine) $\endgroup$
    – Daniel
    Dec 20 '18 at 22:59

Your Answer

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

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