The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\in \mathbb{Z}_q^{(n+1)\times m}$ and uniformly random $x \in \{0,1 \}^m$, the term $Ax\in \mathbb{Z}_q^{n+1}$ is close to uniform.

Now, I'm a little confused. I see no difference between this lemma and the hardness of decisional SIS problem. I think the condition on $m$ is also for being able to guarantee the existence of a solution for the corresponding SIS problem (and so having the right version of this problem).

Can someone explain this?


1 Answer 1


The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random. In particular, this implies that for uniformly random $(A,u)$, there exists a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability. For if not, a significant fraction of $u$ values would admit no solution, hence the distribution of $Ax$ would not be close to uniform, because it never produces any of those $u$ values. (In fact, most $u$ will typically have many solutions.)

All the above is unconditional---we're not relying on any assumptions about whether a problem is hard or not, we're just making statements about probability.

The "decisional SIS problem" is not a standard concept, because it's not so meaningful. If one were to define it, the problem would ask to distinguish between $(A,u=Ax)$ and uniformly random $(A,u)$. But by the above we know that's just impossible: the two distributions are very close, so they can't be told apart.

The computational SIS problem (in its inhomogeneous version) asks, given uniformly random $(A,u)$, to find some short (e.g., binary) $x$ such that $Ax=u$. Again, the choice of $m$ is such that solution(s) exist with very high probability; the computational question is whether we can efficiently find a solution.

The SIS problem is believed to be hard, thanks to much supporting evidence (e.g., reductions from worst-case lattice problems). However, we can't rule out the possibility that SIS actually is easy, but we just haven't yet found an efficient algorithm to solve it. Yet even if SIS were easy, that would not contradict any of the above probability statements; it would just mean that we can efficiently find a solution among the several that are likely to exist.


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.