Hot answers tagged

15

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(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence $\eta_{2^{-n}}(L) = O(1)$ but $\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$. The statement and proof of ...


13

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 that $q$ is prime, and suppose that the minimum distance in the 2-norm is indeed bounded by $b=O(1)$. There are at most $Binom[m,b] \cdot (2b+1)^b = poly(m)$ ...


10

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 a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability. For if not, a significant fraction of $u$ values would admit no solution, hence the ...


8

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 $SIVP_\sqrt{n}$ to $SIS$ while in the second paper, $SIVP_c$ is proven to be NP-Hard for any constant $c$. Until now, there is no proof that $SIVP_\sqrt{n}$ is NP-...


5

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$ (where $\Lambda$ is a lattice), the associated $\delta$ (often also denoted by $\delta_0$) is defined to be such that $\| \mathbf{v} \| = \delta^n \det(\...


5

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 this lattice, it implies that you found a vector $v$ (actually many such vectors) such that $Av=0\bmod\,p$ and $||v||\leq \gamma\cdot\lambda_m(\mathcal{L}).$ ...


5

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 its basis is not the matrix $A$. To construct a basis to this lattice, one usually suppose that $A$ has $n$ linearly independent columns (let's say, the first $...


4

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. Basically, flatten Z and B into integer vectors, and take the inner product. Sorry, it should have been defined. And also, in Figure 1, where this rejection ...


3

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 like a uniformly random vector in $\mathbb{Z}_q^n$. If you want to fix ideas, assume $3$ divides $q$ and $\alpha =1$: then $(2\alpha+1)t$ always has its entries a ...


3

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 \mathbb{Z}_q^m$ such that $||\vec x|| \leq \beta$ and $A\cdot \vec x = \vec 0$. The matrix $A$ specifies an instance of this general SIS problem. You get ...


3

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 parallels between the worlds of lattices and codes, these parallels are not exact. A particular example is the hardness of computing the "smallest element" of ...


3

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 lattice a Hermite approximation factor of $C^k$ for lattice reduction algorithms (LLL/BKZ) over a lattice of dimension $k$ noting that one can `ignore columns' ...


3

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\} \supset q \mathbb{Z}^m$. Thus it is not the same as your $L(B)$. On the other hand, showing that SIS is as hard as certain lattice problems is not obvious and ...


2

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 $\xi_i$ are uniformly random? For any $\ell \ge 2$, there will be values of $\gamma$ and $\xi_i$ for which there are multiple solutions; one such set of values ...


2

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/latticeNISZK.pdf Getting NIZK from lattices is a major open problem. (As far as we know, you might have to go all the way up to multilinear maps and IND obfuscation for ...


2

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 contrary, Regev's one is typically used in an injective regime. And we do know how to build and encryption scheme from it. Regarding Hardness, solving SIS over ...


1

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 hard for an appropriate choice of parameters. Let $q=2^\ell$ be a power of 2 that is sufficiently larger than $\beta$. Let $n'=n/\ell$ (we assume $n$ divisible by ...


1

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^{m-m'}$. Then, $$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$ So, given an instance of SIS, that is, an $n\times m$ matrix $A$, if you have an oracle to solve ...


1

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 = A' x = B' x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.


1

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 knowledge (not a proof of knowledge) but there seems to be little practical difference between the two. If you dislike non-falsifiable assumptions, you could ...


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