# average-case SIS and average-case BDD

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?

• what does "just include some case of" mean? Apr 16 '20 at 11:26
• 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 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.