What is a sparse subset? In a work about fully homomorphic encryption I found usage of the expression: "sparse subset", as in: > Our hint will consist of a set of vectors that has a (secret) sparse subset of vectors whose sum is **v** $_J^{sk^*}$ How exactly is such sparseness defined in general? Or it is a notion created by Craig Gentry and it just means that there are _not that many_ vectors and that distances between them are _fairly big_?

Sparse here means the following: $S\subseteq T$ (where $T$ is finite, and has size $n=|T|$ for $n$ considered as going to infinity) is _sparse_ if $\frac{|S|}{|T|} = o(1)$. See e.g. an example on the last line of p.16.