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}})}$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
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
