Hot answers tagged

14

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


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

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 $...


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

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 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

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


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