Tag Info

New answers tagged


Examining the definition provided by A. Sakzad, I now have the intuition for what this means which I'll explain through an example. In the diagram below, the red dots are a lattice, and the two red arrows represent a basis, $B$, for this lattice. We have a green vector, $ψ'$ = [2, 2]. We might ask which point on the lattice $ψ'$ is closest to. If we are ...


It can be defined as follows: $$\psi = \psi' \pmod{\bf B} = \psi'-{\bf B}\cdot\lceil{\bf B}^{-1}\psi'\rfloor,$$ where $\lceil\cdot\rfloor$ denotes the round operation to the nearest integer.


The main advantage of using $q$-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems. So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness ...


As you write, an algorithm for SVP$_\gamma$ must output a nonzero lattice vector $v \in L$ such that $\| v \| \leq \gamma \cdot \lambda_1(L)$, where $\lambda_1(L)$ denotes the minimum distance of $L$. It is also true that we don't have an efficient algorithm to verify that a candidate $v$ meets this condition, because $\lambda_1(L)$ appears hard to compute. ...

Top 50 recent answers are included