Questions tagged [sis]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
32 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 ...
user avatar
  • 325
1 vote
0 answers
40 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 ...
user avatar
  • 11
1 vote
1 answer
93 views

Frobenius inner product polynomial rings

I'm trying to implement the zero-knowledge proof presented in this paper. The proof has a rejection step (page 14), which can be computed as follows: Where B and Z are in $R^{m \times n}$ for some ...
user avatar
2 votes
1 answer
173 views

SIS vs LWE Problem

The Ajtai one way function is defined by $$f_A(x)= Ax \; mod\; q $$ where the x $\in \{0,1\}^m$ and A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ is one way function ( Ajtai 96) While the Regev One way ...
user avatar
3 votes
1 answer
142 views

SIS without the modulus

Consider the following modification to the Short Integer Solution (SIS) problem: Let $n$ be an integer and $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ be functions of $n$. Sample ...
user avatar
  • 141
3 votes
1 answer
272 views

The equivalence of SIS and ISIS(Inhomogeneous SIS)

I would like to know whether these two problems are equivalent or not, namely: $SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
user avatar
1 vote
1 answer
96 views

Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$. Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$. Here, $k \geq m>...
user avatar
1 vote
1 answer
42 views

Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows. Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
user avatar
2 votes
1 answer
75 views

average-case SIS and average-case BDD

In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{...
user avatar
7 votes
1 answer
207 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
user avatar
  • 408
6 votes
1 answer
183 views

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$. ...
user avatar
6 votes
1 answer
1k views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
user avatar
2 votes
0 answers
80 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$ ...
user avatar
2 votes
1 answer
131 views

Why does the following SIS-based decision language not make sense?

I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and ...
user avatar
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 ...
user avatar
2 votes
1 answer
127 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
user avatar
10 votes
2 answers
1k views

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
user avatar
  • 8,677
3 votes
1 answer
54 views

Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over ...
user avatar
  • 3,802
3 votes
2 answers
303 views

How is the matrix A related to the lattice space L in SIS?

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
user avatar
  • 93
3 votes
0 answers
62 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 ...
user avatar
6 votes
1 answer
496 views

Hardness of Short Interger Solution in Lattices

Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as: Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| ...
user avatar
  • 869
2 votes
0 answers
184 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 ...
user avatar
  • 869
3 votes
0 answers
327 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 ...
user avatar
  • 990
4 votes
1 answer
220 views

Is there any reduction from Short Integer Solution to $\textrm{SIVP}_\gamma$

Short Integer Solution (SIS) is proved to be hard by reducing $\textrm{SIVP}_\gamma$ to SIS, i.e., if we solve SIS, then we can solve $\textrm{SIVP}_\gamma$. Is there any way to reduce an instance of ...
user avatar
  • 869
7 votes
1 answer
683 views

Relation between decisional SIS and leftover hash lemma in lattices

The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
user avatar
  • 990
5 votes
1 answer
975 views

How to estimate the hardness of SIS instances?

The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}...
user avatar
  • 1,370
5 votes
2 answers
313 views

ZK Proof for SIS

Let $A x = 0 \bmod q$ with $\Vert x \Vert < \beta$ as part of a lattice SIS problem. Does there exist an efficient zero knowledge proof of knowledge for such a solution? My idea is to use it for ...
user avatar