# Parameters for high density SIS

I am considering the SIS problem of finding $$x\in \mathbb{Z}^m$$ such that for random $$A\in\mathbb{Z}_q^{n\times m}$$, $$Ax=0$$ and $$\lVert x\rVert < \beta$$ for some $$p$$-norm and bound $$\beta < q$$. High density is when $$n\log_2(q) \ll m$$, or more generally when input is significantly larger than output.

## General methodology

The tightest reduction I know of from SIS to worst-case lattice problems comes from [MP13] which provides nearly optimal asymptotic parameters. But papers (like this) that implement SIS select parameters by following [MR08], which analyzes the cost of the random ($$q$$-ary) $$m$$-dimensional lattice problem, ignoring the reduction to, and cost of the respective worst-case $$n$$-dimensional lattice problem. Does this mean that average-to-worst-case reductions are only of theoretical, asymptotic interest and not relevant when selecting practical, concrete parameters? Is the (sole) value of average-to-worst-case reductions a reassurance that attack algorithms will not significantly improve in the future?

If this is indeed the case then I will also follow [MR08] below in an effort to select safe parameters for high density SIS (in order to construct a highly compressive collision-resistant hash). I will consider the infinite norm with bound $$d.

## Avoiding lattice reduction attacks

In reasonable time one may select any subset of $$c$$ columns of $$A$$ and find a solution $$x$$ with $$\lVert x\rVert_2 \geq q^{n/c}\delta^c$$ by setting coordinates for ignored columns to $$0$$. (I think $$\delta$$ is called the "root Hermite factor"). An $$x$$ with $$\lVert x\rVert_\infty < d$$ will have $$\lVert x\rVert_2 \leq \sqrt{c(d-1)^2}$$. Thus it seems sufficient to set the constraint $$\forall c\in[m]: q^{n/c}\delta^c > (d-1)\sqrt{c}$$. This can be modified to $$\forall c\in[m]: n\log_2(q) > c\log_2((d-1)\sqrt{c}/\delta^c)$$.

## Avoiding combinatorial attacks

For the smallest integer $$k$$ satisfying $$\frac{2^k}{k+1} \geq \frac{m\log_2(2(d-1)+1)}{n\log_2(q)}$$ one can find solution $$x$$ with $$\lVert x\rVert_\infty < d$$ in time $$(2(d-1)+1)^{m/2^k}$$. Thus for security parameter $$s$$ we add the constraint $$(2(d-1)+1)^{m/2^k} \geq 2^s$$.

## Avoiding all attacks

Are the above constraints sufficient? Do I also need to analyze the cost of the best high density subset-sum algorithms? An example of parameters (achieving hash compression factor $$6000$$) is $$d=64 \\ m=2 \times 10^6 \\ n\log_2(q) = 2\times 10^3$$ For $$\delta=1.01$$ (could be reduced for quantum algorithms) the maximum of $$c\log_2((d-1)\sqrt{c}/\delta^c)$$ is about $$1800$$ at about $$c=400$$. Thus the first constraint is satisfied with $$n\log_2(q) = 2000 > 1800 = max_c\{c\log_2((d-1)\sqrt{c}/\delta^c)\}$$ For $$k=17$$ $$\frac{2^k}{k+1} = 7281 \geq 6989 = \frac{m\log_2(2(d-1)+1)}{n\log_2(q)}$$ So the cost is $$(2(d-1)+1)^{m/2^k} = 2^{m\log_2(2(d-1)+1)/2^k} = 2^{106}$$ offering $$106$$ bits of security. Note the precise values of $$n$$ and $$q$$ are left free subject to $$n\log_2(q) = 2\times 10^3$$ and $$q > 64$$.

## Questions

As I asked above, what is the general methodology? How should I select safe parameters for high-density SIS? If the criteria of [MR08] is not enough, what constraints are lacking? If the criteria are enough, am I free to choose any parameters satisfying these constraints, no matter how tight the inequalities (e.g. $$d = q-1$$)?

## References

[MR08]: Lattice-based Cryptography (https://cims.nyu.edu/~regev/papers/pqc.pdf)

[MP13]: Hardness of SIS and LWE with Small Parameters (https://web.eecs.umich.edu/~cpeikert/pubs/LWsE.pdf)