# Questions tagged [sis]

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

25 questions
Filter by
Sorted by
Tagged with
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 ...
569 views

415 views

287 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 ...
53 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 ...
102 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 ...
61 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 ...
318 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 ...
58 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}_{...
107 views

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\| \... 1answer 113 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 ... 0answers 67 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$... 1answer 111 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}$... 0answers 154 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 ... 1answer 36 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 ... 1answer 44 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 ... 1answer 91 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>...
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 ...
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 ...