average-case SIS and average-case BDD

Question

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?

Answer 1

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.