2
$\begingroup$

In an algebraic number field, an ideal $I$ in the ring of integers $\mathcal{O}_K$ has dual $I^\vee = \{x\in\mathcal{O}_K\text{ : }T_{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I\}$, where $T_{K/\mathbb{Q}}(\cdot)$ is the field trace. A lattice $\mathcal{L}$ in $\mathbb{R}^n$ has dual $\mathcal{L}^\ast = \{x\in\mathbb{R}^n\text{ : }\langle x,y\rangle\in\mathbb{Z}\text{ for all }y\in\mathcal{L}\}$, where $\langle\cdot,\cdot \rangle$ is an inner product. From page 14 of the RLWE paper, where $\sigma$ is the canonical embedding and $\mathcal{L}\subset K$:

It is not difficult to see that, under the canonical embedding, $\mathcal{L}^{\vee}$ embeds as the complex conjugate of the dual lattice, i.e., $\sigma\left(\mathcal{L}^{\vee}\right)=\overline{\sigma(\mathcal{L})^{*}}$. This is due to the fact that $\operatorname{Tr}(x y)=\sum_{i} \sigma_{i}(x) \sigma_{i}(y)=\langle\sigma(x), \overline{\sigma(y)}\rangle$.

My question is: why is the dual ideal $I^\vee$ used in RLWE? Is it because of the presence of the quantum Fourier transform in the proof of Lemma 3.14 of the original LWE paper? Or is it so that Lemma 4.7 of RLWE (the reduction from BDD to RLWE) is correct? Or because of some other reason?

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that you don't strictly need the dual ideal for RLWE's security, you just take an efficiency hit if you don't use it. See page 4 of Algebraically Structured LWE, revisited for some commentary on this. It does show up in the "Bounded Distance Decoding on the dual -> Discrete Gaussian Sampling on the primal -> BDD on the dual -> $\dots$" chain of reductions, which is key to the worst-case to average-case reduction. Roughly speaking, lemma 3.14 is one of these steps (using the quantum fourier transform to show that BDD on the dual implies DGS on the primal), and lemma 4.7 is the other. Both steps involve going from some problem on a lattice to a problem on its dual, but, as I said initially, one can (later) remove this from RLWE via a reduction from Dual-RLWE to Primal-RLWE, at the cost of inflating the size of the error.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.