# 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

Accepted

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

The problem becomes easy (as in `solvable in polynomial time') if $$\beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k}$$ for some constant $C$. This follows from: volume $q^{n}$ for the $q$-ary kernel ...

### 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 ...
Accepted

### What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?

The hardness of SIS (or more precisely, the hardness of the module version of SIS: MSIS) is the assumption used to demonstrated the Strong Unforgeability of Crystal Dilithium under Chosen Message ...
Write $A = [A_1 ~~ A_2]$ with $A_1 \in \mathbb{Z}_q^{n\times m'}$ and $A_2 \in \mathbb{Z}_q^{n\times (m-m')}$. Likewise, $e = (e_1 ~~ e_2)$ with $e_1 \in \mathbb{Z}_q^{m'}$ and $e_2 \in \mathbb{Z}_q^{... 1 vote ### Collision ISIS Problem Answering my own question. I guess the problem has no specific name because it is not different from the SIS problem. Let$C=[A|-B]$and$s=[u|v]$then the problem$A.u=B.v$is equivalent to$C.s=0$... 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 ### Why does the following SIS-based decision language not make sense? 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 =...
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 ...