Input: An $n$-slot integer modulo $t$ vector $\overrightarrow{v}=(v_0,v_1,\cdots ,v_{n-1})\in {\mathbb{Z}}_t^n$

Encoding:

Convert $\overrightarrow{v}\in {\mathbb{Z}}_t^n$ into $\overrightarrow{m}\in {\mathbb{Z}}_t^n$ by applying the transformation $\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot \overrightarrow{v}}{n}}$

, where $\tilde{W}$ is a basis of the $n$-dimensional vector space crafted as follows:

$\tilde{W}=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill ⋮\hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \end{array}\right]$

, where $\omega$ is a primitive $2n$-th root of unity modulo $t$ (which implies $t\equiv 1mod2n$). This implies that $\omega =g^{\frac{t-1}{2n}}modt$ ($g$ is a generator of ${\mathbb{Z}}_t^{\times }$ (see §A-11.6.1). The final output is $M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{m}_i{X}^i\in {\mathbb{Z}}_t[X]∕(X^n+1)$, which we can also treat as

$M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{m}_i{X}^i\in {\mathbb{Z}}_q[X]∕(X^n+1)$ during encryption/decryption later, because the initial fresh coefficients $m_i$ are guaranteed to be smaller than any $q$ where $q=\{q_0,q_1,\cdots ,q_L\}$.

Decoding: For the plaintext polynomial $M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{m}_i{X}^i$, compute $\overrightarrow{v}={\tilde{W}}^{\ast }\cdot \overrightarrow{m}$, where

${\tilde{W}}^{\ast }=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(1)})\hfill & \hfill {({\omega }^{J(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(2)})\hfill & \hfill {({\omega }^{J(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(1)})\hfill & \hfill {({\omega }^{J_{\ast }(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(2)})\hfill & \hfill {({\omega }^{J_{\ast }(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill \end{array}\right]$