Questions tagged [sis]

For questions involving/related to the Short Integer Solutions(SIS) problem.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
63 views

Size of $q$ in reductions from lattice problems to R-SIS

The Short integer solution problem is parameterized by four values: $n$, the dimension of the vectors that must be added $m$, the number of samples (dimension of the solution) $\beta$, upper-bound ...
3 votes
0 answers
329 views

Short integer solution lattice problem with q=2

For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is ...
  • 990
2 votes
0 answers
81 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
2 votes
0 answers
187 views

Hardness of $SIS$ and its reduction to an NP-complete problem

Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$ Is $SIS\in NP$ ? If $SIS \in NP$, then it ...
  • 879
1 vote
0 answers
36 views

non-prime modulus for Ring-SIS

Consider the Ring-SIS problem for $R_q=\mathbb{Z}_q[x]/(x^n+1)$ when $n$ is power of $2$ and $q=1 \mod 2n$. Does the modulus $q$ need to be prime? if yes, it seems that it is mainly because of the way ...
  • 325
1 vote
0 answers
47 views

polynomial time reduction from SIS to decisional-LWE?

Is the claim "If there is an efficient algorithm that solves SIS, then there is an efficient algorithm that solves decisional LWE" is sufficient? or, Is the claim above is equivalent to the ...
  • 11
1 vote
0 answers
75 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...