# Tag Info

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

1

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.

2

It is equally difficult (within a factor of 2) for any irreducible polynomial. Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly. Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$

1

To do EEA on a finite-field, you can't perform the operations using the operations in the ring of the integers (and they're not precisely the same operations in the field either, as you're working with bit vectors, not field elements). In particular: When you do "addition", you need to perform the addition as done in even characteristic fields (that is, ...

Top 50 recent answers are included