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?

Screenshot of the section in that paper


1 Answer 1


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.

  • 1
    $\begingroup$ Thank you! That helped $\endgroup$
    – Alcedias
    Nov 3, 2020 at 3:36

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.