# Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography

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

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

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.

• Thanks a lot, it is clear to me now. Truly appreciate your reply. Sep 1, 2023 at 1:35
• Glad you liked it, hope you don't mind accepting the answer, means a lot :D Sep 1, 2023 at 5:50
• 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 :( ) Sep 14, 2023 at 2:15