# [Questions about a proof in the prelim of paper "Lattice-Based Zero-Knowledge Proofs and Applications"]

May I ask that in section 2.7 challenge space in the paper Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General

What is rot(c), why does rot(c) $$\in Z^{d*d}$$, and why |rot(u)|2 <= |u|2 ?
And may I also ask that what is $$S_{k}^{\delta}$$ Also, I am new to lattice crypto, I would truly appreciate it if someone pointed out some resources of learning the math behind ring theory that is essential to read these papers? Thanks a lot

$$rot(c)$$ is the matrix defined by the rotation matrix depending on the number field you are working in, in the paper the number field is $$K = \mathbb{Q}[X]/(X^d+1)$$ which has a ring of integers $$R = \mathbb{Z}[X]/(X^d+1)$$ and $$R_q= \mathbb{Z}_q[X]/(X^d+1)$$.

Let $$\left\{X^i | i\in \left\{ 0,\ldots ,d-1 \right\}\right\}$$ be a basis of $$R_q$$.

the $$rot$$ is defined to be the rotation matrix that send $$a = \sum_{i=0}^{d-1}{a_iX^i} \in R_q$$ to $$\begin{bmatrix} |&|&|&|\\ a*1 & a*X &\cdots& a*X^{d-1}\\ |&|&|&| \end{bmatrix}$$ such that $$a*x^i = \begin{bmatrix} a_{0+i\mod d}\\ a_{1+i\mod d}\\ \vdots\\ a_{d+i\mod d}\\ \end{bmatrix}$$

### Example

if $$d=4$$ then

for an element $$a = a_0+a_1X+a_2X^2+a_3X^3$$ of $$R_q$$ $$rot(a)= \begin{bmatrix} a_0 & -a_3 & -a_2 & -a_1\\ a_1 & a_0 & -a_3 & -a_2 \\ a_2 & a_1 & a_0 & -a_3\\ a_3 & a_2 & a_1 & a_0\\ \end{bmatrix}$$

now it is clear why the $$|rot(u)|_2 \leq |u|2$$ from the definitions in page 11 and the fact that $$\Vert u\Vert ^2 = \Vert rot(u) u \Vert$$ which is smaller than $$\Vert rot(u)\Vert \Vert u \Vert$$ thus the result. for the last question you can find a good library in https://thelatticeclub.com/

My previous answer gives intuition on what $$\mathbf{rot}(a)$$ is, which you might find useful.