2
$\begingroup$

I am currently reading "A Decade of Lattice Cryptography" At page 30, section 4.3.2, it descrip left multiplication by any fixed ring element a
enter image description here

It mention something about curcilant matrix whose first column is the coefficient vector a. I am confused why multiply a circulant matrix will yield a SIS instance? Can someone kindly explain it?
Thanks a lot

$\endgroup$

1 Answer 1

5
$\begingroup$

The important sentence/fact used here is

Any $a \in \mathcal{R}_q$ is a $\mathbb{Z}$-linear function from $\mathcal{R}$ to $\mathcal{R}_q$, so it can be represented by a square matrix $\mathbf{A}_a \in \mathbb{Z}_q^{n \times n}$.

First, note that $\mathcal{R} \leftrightarrow \mathbb{Z}^n$. For example, we can easily see $\mathcal{R} = \mathbb{Z}[x] / (x^n - 1)$ is isomorphic to $\mathbb{Z}^n$: There is a (linear algebraic) basis $\{1, x, \cdots, x^{n - 1}\}$ of $\mathcal{R}$, so we can identify their coefficients as a vector. Take $n = 4$ and $\mathcal{R} = \mathbb{Z}[x] / (x^4 - 1)$. Then, the element $a = 3 - 5x + 27x^2 + x^3$ is identified by $(3, -5, 27, 1) \in \mathcal{R}$. This is called the coefficient embedding. Note that this works for other rings, say $\mathbb{Z}[x] / (f(x))$ for any polynomial $f$.

Now, consider a fixed element $a = a_0 + a_1x + \cdots + a_{n - 1}x^{n - 1} \in \mathcal{R}$ and a varying element $b = b_0 + b_1x + \cdots + b_{n - 1}x^{n - 1} \in \mathcal{R}$. To multiply them, we can write

$$ \color{blue}{ab = \sum_i b_i (ax^i)} $$

Here comes the important part: the term $ax^i$ is fixed! In the case of $\mathcal{R} = \mathbb{Z}[x] / (x^n - 1)$, it even has a particularly easy to see form. Indeed,

\begin{align*} i = 0 \implies ax^i &= a_0 + a_1x + \cdots + a_{n - 1}x^{n - 1}\\ i = 1 \implies ax^i &= a_0x + a_1x^2 + \cdots + a_{n - 1}x^n \\ &= a_{n - 1} + a_0x + a_1x^2 + \cdots + a_{n - 2}x^{n - 1}\\ i = 2 \implies ax^i &= a_0x^2 + a_1x^3 + \cdots + a_{n - 1}x^{n + 1} \\ &= a_{n - 2} + a_{n - 1}x + a_0x^2 + \cdots + a_{n - 3}x^{n - 1} \end{align*}

If the structure is not clear, perhaps writing them in vector form will be clear: performing the coefficient embedding we described, we have

\begin{align*} i = 0 \implies ax^0 &= (a_0, a_1, \cdots, a_{n - 1}) \\ i = 1 \implies ax^1 &= (a_{n - 1}, a_0, a_1, \cdots, a_{n - 2}) \\ &\vdots \\ i = n - 2 \implies ax^{n - 2} &= (a_2, a_3, \cdots, a_{n - 1}, a_0, a_1) \\ i = n - 1 \implies ax^{n - 1} &= (a_1, a_2, \cdots, a_{n - 1}, a_0) \\ \end{align*}

Finally, to link this to $\color{blue}{ab = \sum_i b_i(ax^i)}$, we observe that by packing $(ax^0, ax^1, \cdots, ax^{n - 2}, ax^{n - 1})$ into (the columns of) matrix $\mathbf{A} = (ax^0 | ax^1 | \cdots | ax^{n - 2} | ax^{n - 1})$, then

$$ ab = \sum_i b_i \underbrace{\mathbf{A}_i}_{\text{column}} = \mathbf{A}_i \begin{pmatrix} b_0 \\ b_1 \\ \cdots \\ b_{n - 1} \end{pmatrix} $$

The matrix $\mathbf{A}$ described here is exactly what the authors mean by "any $a \in \mathcal{R}_q$ is represented by a square matrix $\mathbf{A} \in \mathbb{Z}^{n \times n}$". As you can see, this is also why the matrix is circulant.

Hope this helps and isn't too long, I am not sure what you know and don't :)


Note 1: This can be done for any ring $\mathcal{R}$ - we say it is a $\mathbb{Z}$-module. However, the matrix $\mathbf{A}_a$ will not necessarily be circulant.

Note 2: There are embeddings apart from the coefficient embedding I described above. For example, the Minkowski embedding is used in cryptography a lot. In the case of cyclotomic rings it's also convenient, since the two embeddings are equivalent even when considering angles (orthonormal basis). But I will leave that for later. Pretty sure it's described in the survey.

Note 3: The map $\mathcal{R} \to \mathbb{Z}^n$ is usually denoted $\mathbf{rot}$ in the academia.

$\endgroup$
3
  • $\begingroup$ Thanks a lot, it is clear to me now. Truly appreciate your reply. $\endgroup$
    – js wang
    Sep 1, 2023 at 1:35
  • 1
    $\begingroup$ Glad you liked it, hope you don't mind accepting the answer, means a lot :D $\endgroup$
    – Gareth Ma
    Sep 1, 2023 at 5:50
  • $\begingroup$ Ha, two weeks later and I am back here looking at my own answer. (I mixed up coordinate and Minkowski embedding, thought the first one preserves norms :( ) $\endgroup$
    – Gareth Ma
    Sep 14, 2023 at 2:15

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.