Distortion of the spherical gaussian error through the canonical embedding in Ring - LWE

In the paper, "On Error Distributions in Ring-based LWE" by Castryck, Iliashenko and Vercauteren, page 3, It is shown that the distrotion to the spherical gaussian in Ring - LWE is caused by the inverse of the vandermonde matrix and the matrix of multiplication by f'(x). It is explicitly stated that the inverse of Vandermonde matrix B is converted into a real matrix by a "easy unitary transformation". Can anyone help me out in figuring how get such a unitary transformation that takes a complex matrix to a real one?

1 Answer

The section you quote is from the introduction. The paper goes into more technical detail later. For example, equation 3.1 states (roughly) the same equation, and then states that:

$$B = U\Sigma$$

Where $$\Sigma$$ is the matrix of the canonical embedding, expressed relative to the basis $$\{\alpha_1,\dots, \alpha_n\}$$, and $$U$$ is the matrix (defined on page 5):

$$U = \begin{pmatrix} I_{s\times s} & 0 & 0 \\ 0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{i}{\sqrt 2}I_{t\times t}\\ 0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{-i}{\sqrt 2}I_{t\times t} \end{pmatrix}$$

$$U$$ is unitary, and known to be an isomorphism $$(H, \langle\cdot, \cdot\rangle_H)\cong (\mathbb{R}^n, \langle\cdot, \cdot\rangle)$$, where $$\langle x,y\cdot\rangle_H = \sum_i x_i\overline{y_i}$$ is the Hermitian inner product, and $$H$$ is a certain conjugation-invariant subspace of $$\mathbb{C}^n$$ that contains the image of the canonical embedding. This is all discussed on page 5.

• Thank you! That helped – Alcedias Nov 3 '20 at 3:36