Score:2

The significance of duals in RLWE

cn flag

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?

Score:1
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.