15
votes
Accepted
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(...
- 5,773
13
votes
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
Independently of the algorithmic claim, I indeed have serious doubts about Theorem 2. Here is a counterargument (using standard techniques) cooked up with Yang Yu and Wessel van Woerden:
Suppose ...
- 1,203
10
votes
Accepted
Relation between decisional SIS and leftover hash lemma in lattices
The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random. In particular, this implies that for uniformly random $(A,u)$, there exists ...
- 5,773
8
votes
Hardness of Short Interger Solution in Lattices
No, we cannot say that Short Integer Solution ($SIS$) problem is NP-Complete.
The results from those two papers are not directly related like that, because on the first one, the reduction is from $...
6
votes
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$...
- 199
5
votes
Accepted
Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography
The important sentence/fact used here is
Any $a \in \mathcal{R}_q$ is a $\mathbb{Z}$-linear function from $\mathcal{R}$ to $\mathcal{R}_q$, so it can be represented by a square matrix $\mathbf{A}_a \...
- 350
5
votes
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 ...
- 1,136
5
votes
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 ...
4
votes
Accepted
Is LPN not as important as LWE and SVP?
LPN is code-based problem, not a lattice problem. These are quite similar, but are defined with respect to different notions of "distance" (Hamming vs $\ell_p$-norm). In general while there are broad ...
- 11.7k
4
votes
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. ...
- 1,136
3
votes
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 ...
- 246
3
votes
Accepted
average-case SIS and average-case BDD
If you want, one can define a "general SIS problem", with parameters $(n,m,q, \beta)$, as follows: I give you a matrix $A\in\mathbb{Z}_q^{n\times m}$, and you must find a nonzero vector $\vec x \in \...
- 19.2k
3
votes
How is the matrix A related to the lattice space L in SIS?
If you are solving a SIS instance $As = 0$ over $\mathbb{Z}_q$ then this can be seen as finding a short non-zero vector from the lattice $\{z \in \mathbb{Z}^m \ \mid Az = 0 \in \mathbb{Z}_q^n\} \...
- 133
2
votes
ZK Proof for SIS
If you are interested in lattice-based (..and non-interactive..) zero knowledge, the state-of-the-art is from a 2008 paper (yes, 2008..) found here: https://web.eecs.umich.edu/~cpeikert/pubs/...
- 560
2
votes
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$, where $\gamma$ and the $\...
- 145k
2
votes
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 ...
- 1,203
2
votes
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,203
2
votes
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 ...
- 21.9k
2
votes
Accepted
The equivalence of SIS and ISIS(Inhomogeneous SIS)
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 ...
- 141
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 =...
- 1,203
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 ...
- 4,626
Only top scored, non community-wiki answers of a minimum length are eligible