Hot answers tagged

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(...
user avatar
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 ...
user avatar
  • 1,119
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 ...
user avatar
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 $...
user avatar
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$...
user avatar
  • 199
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 ...
user avatar
  • 1,126
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 ...
user avatar
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. ...
user avatar
  • 1,126
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 ...
user avatar
  • 236
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 \...
user avatar
3 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 ...
user avatar
  • 8,677
3 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 ...
user avatar
  • 1,119
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\} \...
user avatar
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^{...
user avatar
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/...
user avatar
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 $\...
user avatar
  • 133k
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 ...
user avatar
  • 1,119
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 ...
user avatar
  • 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 =...
user avatar
  • 1,119
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 ...
user avatar
  • 4,546

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