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


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$)?


[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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.