In Micciancio and Regev's paper "Lattice-based Cryptography",the length of the shortest vector is at least $\min\{q, 2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}\}$ . I want to ask why the paper chose the latter as the length of the shortest vector rather than $q$ when considering concert parameters. In addition, whether the $q$ is normally more than $2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}$?


Remember that we are considering $q$-ary lattices, as defined by

$$ \Lambda^{\perp}_q(\mathbf{A}) = \{ \mathbf{y} \in \mathbb{Z}^m : \mathbf{A} \mathbf{y} = \mathbf{0} \mod q \}. $$

Clearly the vector $(q,\mathbf{0})$ is in this lattice, and has length $q$. This is a trivial, uninteresting solution, as it doesn't give a better understanding of the lattice.

$\min \{ q, 2^{2 \cdot \sqrt{(n\cdot \log{q} \cdot log{\delta})}} \}$ refers to the shortest vector one can find using (then) state of the art lattice reduction algorithms. If you're choosing parameters in order to make a cryptographic scheme secure, you are trying to ensure that the shortest non-trivial vectors that can be found are not very short. If trivial vectors break your scheme, it is broken anyway, and no amount of parameter tweaking will fix it.


There are a few works about concrete parameters for lattice cryptography, e.g.:

  • R. Lindner and C. Peikert, 2010, Better Key Sizes (and Attacks) for LWE-Based Encryption
  • M. Rückert and M. Schneider, 2010, Estimating the Security of Lattice-based Cryptosystems (http://eprint.iacr.org/2010/137) (in Peikert's works it seems this is referenced with the title Selecting secure parameters for lattice-based cryptography, maybe it was updated with the new title later)

In the paper by Rückert and Schneider they talk about your referenced paper and proposed numbers in section 4 and table 3 is worth a look. However, tehy also state, that those numbers were chosen with $\delta \geq 1.01$ in mind, which might not be appropriate any more.

But here are example values from that table (entry with year 2035, 92 bits of security):

  • $n = 512$
  • $q = 2^{59.749}$
  • $\delta = 1.0064$

In that case, we would get (with logarithms with base 2):

$$2^{2 \sqrt{n \log{q} \log{\delta}}} \approx 2^{33.5594} < 2^{59.749} = q $$ (If my simple calculator worked correctly)

The reason for this is, that $\delta$ is really close to $1$, which means $\log{\delta}$ is much smaller than $1$, close to $0$.

As final note, there is a recent survey over lattice cryptography from Peikert: Decade of Lattice Cryptography


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.