Questions tagged [sis]
For questions involving/related to the Short Integer Solutions(SIS) problem.
21
questions
2
votes
1answer
65 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\| \...
0
votes
0answers
24 views
Is there decisional version of module-SIS problem?
We have a challenger who computes and gives the adversary the following:
random matrix A sampled from the ring $R^{k \times l}_q$
random vector b from the ring $R^{l}_q$
random vector x from the ring ...
1
vote
1answer
74 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>...
1
vote
1answer
34 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 ...
1
vote
1answer
44 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}_{...
7
votes
1answer
136 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, ...
6
votes
0answers
110 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$. ...
6
votes
1answer
642 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|| \...
2
votes
0answers
60 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
1answer
97 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 ...
1
vote
0answers
63 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 ...
2
votes
1answer
86 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}$ ...
10
votes
2answers
982 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 ...
3
votes
1answer
52 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 ...
3
votes
2answers
255 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 ...
2
votes
0answers
53 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 ...
1
vote
0answers
142 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 ...
2
votes
0answers
304 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 ...
7
votes
1answer
483 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\...
4
votes
1answer
702 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}\}...
5
votes
2answers
278 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 ...
