0
$\begingroup$

Some literature about lattices set $\mathbb{Z}_{q}$ in $[-\frac{q}{2}, \frac{q}{2})\cap \mathbb{Z}$ but not $[0,q-1]$ such as "lattice signatures without trapdoors" and "lattice based blind signatures", I don't know the reason. Thank you for explain the reason for me if you know it.

| improve this question | | | | |
$\endgroup$
2
$\begingroup$

Well, these lattice schemes need to define a 'small vector' $\epsilon$ in such a way that the multiplication of two small vector elements $\epsilon_0 \times \epsilon_1$ is still small; that is, for a random element $A$, we still have $A \approx A + \epsilon_0 \times \epsilon_1$

One way to do this is to define a 'small vector' as one whose elements all have small absolute values; if you define 'small absolute value' tightly enough, then the elements of $\epsilon_0 \times \epsilon_1$ (ignoring the modulus operation) will still probably [1] have terms with absolute values less that $q/k$ (which is 'close enough' - the original schemes had $k=4$).

Of course, you might ask "why don't they define small vectors to have elements with small nonnegative terms?". Well, if they defined the ring over $x^n+1$ (for example), then something strange happens. Element $i$ of $A \times B$ can be expressed as

$$A_iB_0 + A_{i-1}B_1 + … + A_0B_i - A_{n-1}B_{i+1} - A_{n-2} B{i+2} - … - A_{i+1} B_{n-1}$$

Specifically, there are $n-i$ terms which are added to the final product, and $i$ terms which are subtracted from the final product.

For small $i$, there are a large number of added terms; if $A, B$ consists of small nonnegative elements, then the result will be strongly weighted toward the positive. For large $i$ (just a bit smaller than $n$), the result will be strongly weighted toward the negative. Hence, the result will have a distinct slant, and that's harder to reason with.

In contrast, if with generate $A, B$ with small absolute values (with no bias between positive and negative), no such bias exists; the distribution of the elements of the result is independent of the position within the vector.


[1]: This is where the probability of decryption failure comes in; most systems don't define the error terms small enough that decryption failure can't happen

| improve this answer | | | | |
$\endgroup$
1
$\begingroup$

A slightly different perspective on the matter is that often a lattice $\Lambda\subseteq\mathbb{Z}^n$ is used for its error-correction properties. Lattices are infinite objects, but for efficiency we often assume they're periodic mod some integer (not necessarily prime, despite the choice of variable) $q$, which is known as being $q$-ary. This gets us a finite size representation of the lattice, but it's know that any lattice is $\det(\Lambda)^2$-ary, so such a representation always exists (although generally $q$-ary lattices assume $q$ to be smaller than $\det(\Lambda)^2$). The condition of being $q$-ary can be algebraically stated as $q\mathbb{Z}^n\subseteq\Lambda$. We can consider the operation $\Lambda\bmod q\mathbb{Z}^n$, which has codomain $[-q/2,\dots q/2]^n\cap \mathbb{Z}^n$ (and for the lattice $q\mathbb{Z}^n$, corresponds to reducing each coordinate of $\Lambda$ mod $q$ independently).

This is a geometric answer for why $[-q/2,\dots, q/2]$ is used rather than $[0, q-1]$. While they can both be seen as ways to represent $\mathbb{Z}/q\mathbb{Z}$ within $\mathbb{Z}$, the former is the fundamental Voronoi cell of the lattice $q\mathbb{Z}^n$ (alternatively, the set of elements closer to $0$ than any other point in $q\mathbb{Z}^n$).

| improve this answer | | | | |
$\endgroup$

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.