# Tag Info

Accepted

Accepted

### How to estimate the hardness of SIS instances?

The value $\delta$ characterizes, how short a vector you can expect to find using an algorithm (typically used in the context of lattice reduction). In particular, for a vector $\mathbf{v} \in \Lambda$...
Accepted

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

If $A\in\mathbb{Z}_p^{n \times m}$, then you can define $$\mathcal{L}=\{y\in\mathbb{Z}^m~:~Ay=0\,\bmod\,p\}.$$ $\mathcal{L}$ is an $m$-dimensional lattice, and if you solve (search) $SIVP_\gamma$ in ...

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

About the basis As stated in the other answer, the lattice directly related to SIS is actually the $q$-ary lattice defined as $$\mathcal{L}_q^\bot(A) := \{ u \in \mathbb{Z}^n : Au = 0 \mod q \}.$$ And ...
Accepted

### Frobenius inner product polynomial rings

Like $||B||^2$ is defined in Section 2.1 to be the norm of the vector of the integer coefficients comprising the elements of $B$, $<Z,B>$ is the inner product of these two integer vectors. ...
Accepted

### Reduction of decison SIS

The assumption about gcd tell you that $2\alpha +1$ cannot belong to an ideal of $\mathbb{Z}/q\mathbb{Z}$. For example, $2\alpha +1$ could divide $q$ and then $(2\alpha+1)t$ is never going to look ...
Accepted

Accepted

### SIS vs LWE Problem

There are important constraint in the parameters for Ajtai's function, that makes it highly surjective (each image has many preimages). We do not know how to get an encryption scheme from that. On the ...
1 vote
Accepted

### SIS without the modulus

It turns out some version of the problem is actually as hard as SIS. Concretely, I claim that the version where $A$ is a random binary matrix and $\beta$ is polynomial will be hard, assuming SIS is ...
1 vote
Accepted

This is equivalent to an LWE language. More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A = [B' | I]$. Then $C^{-1} u =... 1 vote ### ZK Proof for SIS The statement "I know an$x$so that$Ax = 0\,\text{mod}\,q$and$\Vert x\Vert < \beta\$" is plainly in NP, so any zkSNARK can give you such a proof, e.g. this paper. Though, this is an argument of ...

Only top scored, non community-wiki answers of a minimum length are eligible