In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a vector $s\in \mathbb{Z}^{m}_{q} \backslash \{0\}$ such that $As=0$ and $||s||\leq \beta$"

but not instances like this " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a matirx $B\in \mathbb{Z}^{m\times k}_{q} \backslash \{0\}$ such that $AB=C$ and $||B||\leq \beta$". The latter instances are more general and the former instances just include some cases of the latter.

And the same case happens in BDD (bounded-distance decoding) problem. We say that LWE problem is an average-case problem because it just includes some cases of BDD problem.

Did I understand that correctly?

  • 1
    $\begingroup$ what does "just include some case of" mean? $\endgroup$ – Geoffroy Couteau Apr 16 '20 at 11:26
  • $\begingroup$ I have edited the question just now. Maybe you can understand my question easier. My understanding is that average-case SIS probelm is a subset of the general SIS problem. Did I understand that correctly?@GeoffroyCouteau $\endgroup$ – Alex Ideal Apr 16 '20 at 13:28

If you want, one can define a "general SIS problem", with parameters $(n,m,q, \beta)$, as follows: I give you a matrix $A\in\mathbb{Z}_q^{n\times m}$, and you must find a nonzero vector $\vec x \in \mathbb{Z}_q^m$ such that $||\vec x|| \leq \beta$ and $A\cdot \vec x = \vec 0$.

The matrix $A$ specifies an instance of this general SIS problem. You get different variants of the problem by defining how the instance $A$ is chosen. What average-case hardness of SIS means is just that it is assumed to be hard to find (with good probability) a solution to the problem above when the instance is chosen randomly from some distribution of instances. This is in contrast to worst-case hardness, which would be the (much weaker) assumption that the problem is hard to solve for some instance $A$.

Now, when we talk about the SIS problem, by default this refers to the conjectured average-case hardness of the problem I described above, where the distribution over instances is the uniform distribution over $\mathbb{Z}_q^{n\times m}$. You can view this if you like as a special case of a more general family of SIS-problems, where one could consider both average-case hardness for different distributions over instances, or worst-case hardness.

However, the terminology "average-case" has nothing to do with the fact that SIS can be seen as a special case of a more general problem where one attempts to find a small-norm matrix $B$ such that $AB=C$ instead of a small-norm vector $\vec x$ such that $A\vec x = 0$. Note that the first one is also well known (it asks about solving several instances of the inhomogenous SIS problem) and indeed more general if we define $k$ and $C$ to be parameters of the system. But this has nothing to do with the terminology average-case - in fact, you could equivalently discuss average-case hardness and worst-case hardness for the more general problem which you consider as well. And the same goes for BDD and LWE.


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.