0
$\begingroup$

Recall Short Integer Solution:

$\textbf{SIS}_{n, q, \beta, m}$: Given $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, $\vec{b} \in \mathbb{Z}^{n}$, find $\vec{z} \in \mathbb{Z}^{m}$ of norm $||z|| \le \beta$ s.t. $\textbf{A}\vec{z} = \vec{b}$.

We must take $\beta < q$ to avoid trivial solutions and $\beta \ge \sqrt{n \log q}$ to guarantee that a solution exists. Is there any other conditions of $\beta$. In particular, is it secure to set $\beta = q-1$?

$\endgroup$

2 Answers 2

1
$\begingroup$

From a practical perspective, the Lattice Estimator, which is typically used to estimate the practical strength of LWE, has planned support for SIS, and some things implemented already.

For example, you can run the code

SIS.estimate(SIS.Parameters(n=1024, q=8380417, length_bound=8380417 - 1, m=2304, norm=+Infinity))

where the $(n,q,m)$ come from one of Dilithium's parameter sets. This yields an error (which appears to be a bug). Changing the -1 to a -10 yields

lattice  :: rop: ≈2^103.2, red: ≈2^102.1, sieve: ≈2^102.2, β: 251, η: 268, ζ: 624, d: 1680, prob: 1, ↻: 1, tag: infinity

Using the standard length bound for Dilithium's parameter set gives

lattice  :: rop: ≈2^152.2, red: ≈2^151.3, sieve: ≈2^151.1, β: 427, η: 433, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity

So choosing $\beta = q-10$ leads to a large reduction in security, but still parameters that the standard attacks profiled in the lattice estimator would not trivially succeed on.

Note that as the SIS support for the lattice estimator is only planned currently, it is possible that some attacks are not currently profiled.

$\endgroup$
0
$\begingroup$

I think it's too close. MP13 gives the tighest reduction I know of from other lattice problems. It works for any $q \geq \beta \cdot n^\delta$ for some constant $\delta > 0$.

If you let $\beta(n) = q(n) - 1$, then $$ q(n) \geq \beta(n) \cdot n^\delta \iff q(n)/n^\delta \geq q(n) - 1 $$ But $q(n) / n^\delta < q(n) - 1$ when $n^\delta \geq 2$ and $q(n) > 2$, which is the case for all sufficiently large $n$. So the reduction doesn't go through.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.