The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this the "normal representation". However, in lattice based crypto, the elements of the field are represented by $\{-(q-1)/2, \dots, (q-1)/2\}$, let's call this the "lattice representation". What is the difference between these two representations? Why is the second one used in lattice crypto? Would it work if the normal representation was used instead? I would also be very grateful if someone could show an example of how $\mathbb Z_7$'s elements $\{0, 1, 2, \dots, 6\}$ are mapped into the other representation.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ $\mathbb{Z}/q\mathbb{Z}$ is quotient ring, so it's elements are really equivalence classes. How these classes are represented is irrelevant, but it may be convenient to use a specific representation in a specific case. $\endgroup$– AlephCommented Jul 13, 2015 at 9:36
-
$\begingroup$ In lattices the elements are vectors and not just integers (more precisely equivalence classes of vectors. This is along the lines of the modulus for integers, but for vectors). $\endgroup$– tyloCommented Jul 13, 2015 at 10:28
-
$\begingroup$ I'm not voting to close, but you should perhaps at least provide references backing your claim that different representations are used in lattice-based crypto. $\endgroup$– fkraiemCommented Jul 13, 2015 at 18:31
-
$\begingroup$ @fkraiem see link page 6, last paragraph. $\endgroup$– caesarCommented Jul 14, 2015 at 1:39
-
$\begingroup$ Aleph is correct that for most operations, the representation is irrelevant, as long as we used a fixed set of representatives for public quantities (this is important for security). The only time we need to use particular representatives is during decryption, when we need to recover the small integer belonging to the given coset. $\endgroup$– Chris PeikertCommented Jul 14, 2015 at 6:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g., as the parity of $e$ modulo 2). By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover the message) simply by "lifting" $v$ to its integer representative.
If we instead used the representatives $0$ through $q-1$, then the representative of $v$ would often be a little smaller than $q$ (specifically, when $e$ is negative), and would not have the proper parity.
Geometrically, using the correct representatives corresponds to "decoding" the lattice $q\mathbb{Z}$ under small error: given the coset $(v + q\mathbb{Z}) \in \mathbb{Z}_q$, we find the smallest element in the coset, which is $e$.
Many papers conflate $\mathbb{Z}_q$ with its set of representatives, but this can cause confusion about what operations are legal and meaningful. Values that are known to be "small" should be seen as elements of $\mathbb{Z}$, which are then reduced mod $q$ when combined with values from $\mathbb{Z}_q$. When we later want to recover a small value from its coset modulo $q$, we lift/decode to $\mathbb{Z}$ using the proper representatives.
answered Jul 14, 2015 at 6:13
-
$\begingroup$ Can you show how to map the elements of $Z_{7}$ into the lattice representation? $\endgroup$– caesarCommented Jul 14, 2015 at 6:23
-
$\begingroup$ The smallest (by magnitude) integer in $5+7\mathbb{Z}$ is $-2 = 5-7$. More generally, to map $0,\ldots,6$ to the other set of representatives, just subtract $7$ from each value larger than $3$. $\endgroup$ Commented Jul 14, 2015 at 6:27
-
$\begingroup$ So this means that {0, 1, 2, 3, 4, 5, 6} will map to {0, 1, 2, 3, -3, -2, -1}. What I don't understand that, 6 has more magnitude than 4 in the first representation, however, in the second representation it has less magnitude. I would be very grateful If you could provide a source that explains this representation in more details. $\endgroup$– caesarCommented Jul 14, 2015 at 6:37
-
2$\begingroup$ $6$ and $-1$ of course have different magnitudes, but they are both representatives of the same coset of $7\mathbb{Z}$. The point is that it is not meaningful to talk about the magnitude of $\mathbb{Z}_q$ elements, only of particular representatives. The "balanced" set has the smallest representative for every element of $\mathbb{Z}_q$. There's no reference for this; you just have to see it for yourself. $\endgroup$ Commented Jul 14, 2015 at 6:46
$\begingroup$
$\endgroup$
My understanding is that the coefficients of polynomials used in lattice crypto are often sampled from a discrete Gaussian distribution. A Gaussian is centered at 0, which would explain why the elements are represented as elements from the set $\{\frac{−(q−1)}{2},…,\frac{(q−1)}{2}\}$, as you mentioned.
answered Jul 14, 2015 at 3:46