Parameters for high density SIS

Question

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<q$.

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)

Answer 1

I'll answer more broadly the question of how useful worst-case to average-case reductions are in setting parameters in lattice-based cryptography (as there has been more work on this in the LWE side of things). The conclusion of the literature appears to be "not too useful", although there are some conflicting claims (I haven't read things closely enough to know which is wrong though).

Note that this answer won't talk about the broad methodology of how to choose parameters for SIS-based primitives. There (to my knowledge) isn't a "SIS estimator" (similarly to the LWE estimator), which would be ideal. I would therefore point anyone to do an analysis similar to the one you have done, mirroring what is done in NIST PQC round 3 schemes.

Does this mean that average-to-worst-case reductions are only of theoretical, asymptotic interest and not relevant when selecting practical, concrete parameters?

(Mostly) yes. The worst-case to average-case reductions are known to be what is known as "non-tight". The first work pointing this out was Another Look at Tightness 2 (section 6). Roughly speaking, they examine Regev's worst-case to average-case reduction from the perspective of concrete security. This analysis does not lead to compelling security claims. In particular, they find that

Thus, if average-case DLWE can be solved in time $T$ , then Theorem 1 [their concrete form of Regev's reduction] shows that $SIVP_\gamma$ can be solved by a quantum algorithm in time $2^{504}T$.

This is just one work (and one worst-case to average-case reduction). For example, this paper finds that Brakerski's reduction loses a factor $2^{1960}$.

There have been similar works for RLWE, which additionally note that the quantum part of the reduction is particularly inefficient (section 6).

The quantum algorithm $A_2$ is based on Lemma 3.14 of [31], which shows that $n \log R$ logical qubits are required for an ideal $I$, where $R$ is an integer which is at least $2^{3n}\lambda_n(I)$. Since $\lambda_n(I)$ is generally polynomial in $n$, it follows that the number of logical qubits required is about $3n^2$. For $n = 2^{10}$ about 3 million logical qubits will be required. In comparison, factoring a 2048-bit RSA modulus requires roughly 4000 to 5000 logical qubits.

Now, there has been a Masters' thesis that found that one can mildly increase parameters (by a factor $\approx 2$) to obtain meaningful (conrete) security, but the previously linked paper (labelled RLWE) found some flaws in this paper.

There has additionally been work on the SIS worst-case to average-case reduction, which has resulted in vaguely similar results --- one can't concretely use the known reductions to justify security for schemes people actually use.

---

Now that we've discussed why worst-case to average-case reductions aren't (currently at least) concretely useful, we can address the second half of the question.

Is the (sole) value of average-to-worst-case reductions a reassurance that attack algorithms will not significantly improve in the future?

Sort of, but not really. All of the reductions are to $\mathsf{SIVP}_\gamma$ for $\gamma = \Omega(\sqrt{n})$, which is not thought to be NP hard. It is consistent with most "standard complexity theory assumptions" that this problem is poly-time solvable, and therefore lattice-based cryptography is completely broken. Note that there is (under some slightly less standard assumptions) some work towards maybe changing this, but it is preliminary (the approximation factors are currently too small to be applicable).

So attacks can improve, which is annoying. Do worst-case to average-case reductions have any purpose then? The answer is yes.

After identifying a plausible hard problem (such as LWE or SIS), one needs a way to sample instances of the problem. There are typically different distributions one can put on the set of all problem instances, and some distributions may be "easier" than others. This can happen in dramatic ways. Note that this has even happened for some distributions used in lattice-based cryptography, namely

1. extremely low noise rate distributions (with the Arora-Ge attacks) $\approx 2011$, and
2. "skewed" RLWE distributions (with the PLWE attacks $\approx 2015$).

These "bad" instantiations were not supported by worst-case to average-case reductions (even asymptotically). They were also vulnerable to attacks.

Therefore the worst-case to average-case reductions are thought to have some use, namely making sure that we don't choose "structurally bad" distributions to work over. But

1. they can't be used to concretely set parameters in a meaningful way, and
2. concrete parameters chosen often aren't even asymptotically supported by these reductions (meaning if one ignores the tightness issues discussed here).

For this second point, I mean specifically that $\sigma = O(1)$ is typically chosen (which is not supported asymptotically), and people often use LWR with small modulus (which is also not supported).