4
$\begingroup$

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.

$\endgroup$
  • $\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$ – Aleph Jul 13 '15 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$ – tylo Jul 13 '15 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$ – fkraiem Jul 13 '15 at 18:31
  • $\begingroup$ @fkraiem see link page 6, last paragraph. $\endgroup$ – caesar Jul 14 '15 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 Peikert Jul 14 '15 at 6:20
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you show how to map the elements of $Z_{7}$ into the lattice representation? $\endgroup$ – caesar Jul 14 '15 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$ – Chris Peikert Jul 14 '15 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$ – caesar Jul 14 '15 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$ – Chris Peikert Jul 14 '15 at 6:46
4
$\begingroup$

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.

$\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.