D-2.2 Batch Encoding

While the single-value encoding scheme (§D-2.1) encodes & decodes each individual value one at a time, the batch encoding scheme does the same for a huge list of values simultaneously using a large dimensional vector. Therefore, batch encoding is more efficient than single-value encoding. Furthermore, batch-encoded values can be homomorphically added or multiplied simultaneously element-wise by vector-to-vector addition and Hadamard product. Therefore, the homomorphic operation of batch-encoded values can be processed more efficiently in a SIMD (single-instruction-multiple-data) manner than single-value encoded ones.

BFV’s encoding converts an $n$-dimensional integer input slot vector $\overrightarrow{v}=(v_0,v_1,v_2,\cdots v_{n-1})$ modulo $t$ into another $n$-dimensional vector $\overrightarrow{m}=(m_0,m_1,m_2,\cdots m_{n-1})$ modulo $t$, which are the coefficients of the encoded $(n-1)$-degree (or lesser-degree) polynomial $M(X)\in {\mathbb{Z}}_t[X]∕(X^n+1)$.

D-2.2.1 Encoding₁

In §A-10.6, we learned that an $(n-1)$-degree (or lesser degree) polynomial can be isomorphically mapped to an $n$-dimensional vector based on the mapping $\sigma$ (we notate ${\sigma }_c$ in §A-10.6 as $\sigma$ for simplicity):

$\sigma :M(X)\in {\mathbb{Z}}_t[X]∕(X^n+1)\to (M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{2n-1}))\in {\mathbb{Z}}_t^n$

, which evaluates the polynomial $M(X)$ at $n$ distinct $(\mu =2n)$-th primitive roots of unity: $\omega ,{\omega }^3,{\omega }^5,\cdots ,{\omega }^{2n-1}$. Let $\overrightarrow{m}$ be a vector that contains $n$ coefficients of the polynomial $M(X)$. Then, we can express the mapping $\sigma$ as follows:

$\overrightarrow{v}=W^T\cdot \overrightarrow{m}$

, where $W^T$ is as follows:

$W^T=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill (\omega )\hfill & \hfill {(\omega )}^2\hfill & \hfill \cdots \hfill & \hfill {(\omega )}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^3)\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^3)}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^5)\hfill & \hfill {({\omega }^5)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^5)}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{2n-1})\hfill & \hfill {({\omega }^{2n-1})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]$ # $W^T$ is a transpose of $W$ described in §A-10.6

Note that the dot product between each row of $W^T$ and $\overrightarrow{m}$ computes the evaluation of $M(X)$ at each $X=\{w,w^3,w^5,\cdots ,w^{2n-1}\}$. In the BFV encoding scheme, the Encoding₁ process encodes an $n$-dimensional input slot vector $\overrightarrow{v}$ $\in {\mathbb{Z}}_t$ into a plaintext polynomial $M(X)\in {\mathbb{Z}}_t[X]∕(X^n+1)$, and the Decoding₂ process decodes $M(X)$ back to $\overrightarrow{v}$. Since $W^T\cdot \overrightarrow{m}$ gives us $\overrightarrow{v}$ which is a decoding of $M(X)$, we call $W^T$ a decoding matrix. Meanwhile, the goal of Encoding₁ is to encode $\overrightarrow{v}$ into $M(X)$ so that we can do homomorphic computations based on $M(X)$. Given the relation $\overrightarrow{v}=W^T\cdot \overrightarrow{m}$, the encoding formula can be derived as follows:

${(W^T)}^{-1}\cdot \overrightarrow{v}={(W^T)}^{-1}{W}^T\cdot \overrightarrow{m}$

$\overrightarrow{m}={(W^T)}^{-1}\cdot \overrightarrow{v}$

Therefore, we need to find out what ${(W^T)}^{-1}$ is, the inverse of $W^T$ as the encoding matrix. But we already learned from Theorem A-11.4 (in §A-11.4) that $V^{-1}={\displaystyle \frac{V^T\cdot I_n^R}{n}}$, where $V=W^T$ and $V=W$. In other words, ${(W^T)}^{-1}={\displaystyle \frac{W\cdot I_n^R}{n}}$. Therefore, we can express the BFV encoding formula as:

$\overrightarrow{m}={(W^T)}^{-1}\cdot \overrightarrow{v}={\displaystyle \frac{W\cdot I_n^R\cdot \overrightarrow{v}}{n}}$, where

$W=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill (\omega )\hfill & \hfill ({\omega }^3)\hfill & \hfill ({\omega }^5)\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{2n-1})\hfill \\ \hfill {(\omega )}^2\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill {({\omega }^5)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {(\omega )}^{n-1}\hfill & \hfill {({\omega }^3)}^{n-1}\hfill & \hfill {({\omega }^5)}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]$

$=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill (\omega )\hfill & \hfill ({\omega }^3)\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{\frac{n}{2}-1})\hfill & \hfill ({\omega }^{-(\frac{n}{2}-1)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{-3})\hfill & \hfill ({\omega }^{-1})\hfill \\ \hfill {(\omega )}^2\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{\frac{n}{2}-1})}^2\hfill & \hfill {({\omega }^{-(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{-3})}^2\hfill & \hfill {({\omega }^{-1})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {(\omega )}^{n-1}\hfill & \hfill {({\omega }^3)}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{\frac{n}{2}-1})}^{n-1}\hfill & \hfill {({\omega }^{-(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{-3})}^{n-1}\hfill & \hfill {({\omega }^{-1})}^{n-1}\hfill \end{array}\right]$

, where $\omega =g^{\frac{t-1}{2n}}modt$ ($g$ is a generator of ${\mathbb{Z}}_t^{\times }$). In §A-10.6, we learned that $W$ is a valid basis of the $n$-dimensional vector space. Therefore, ${\displaystyle \frac{W\cdot \overrightarrow{v}}{n}}=\overrightarrow{m}$ is guaranteed to be a unique vector corresponding to each $\overrightarrow{v}$ in the $n$-dimensional vector space ${\mathbb{Z}}_t^n$ (refer to Theorem A-10.4 in §A-10.4), and thereby the polynomial $M(X)$ comprising the $n$ elements of $\overrightarrow{m}$ as coefficients is a unique polynomial bi-jective to $\overrightarrow{v}$.

Note that by computing ${\displaystyle \frac{W\cdot I_n^R\cdot \overrightarrow{v}}{n}}$ , we transform the input slot vector $\overrightarrow{v}$ into another vector $\overrightarrow{m}$ in the same vector space ${\mathbb{Z}}_t^n$, while preserving isomorphism between these two vectors (i.e., bi-jective one-to-one mappings and homomorphism on the $\text{(+,⋅)}$ operations).

D-2.2.2 Encoding₂

Once we have the $n$-dimensional vector $\overrightarrow{m}$, we scale (i.e., multiply) it by some scaling factor $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$, where $q$ is the ciphertext modulus. We scale $\overrightarrow{m}$ by $\mathrm{\Delta }$ and make it $\mathrm{\Delta }\overrightarrow{m}$. The $n$ integers in $\mathrm{\Delta }\overrightarrow{m}$ will be used as $n$ coefficients of the plaintext polynomial for RLWE encryption. The finally encoded plaintext polynomial $\mathrm{\Delta }M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\mathrm{\Delta }{m}_i{X}^i$.

D-2.2.3 Decoding₁

Once an RLWE ciphertext is decrypted to $\mathrm{\Delta }M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\mathrm{\Delta }{m}_i{X}^i$, we compute ${\displaystyle \frac{\mathrm{\Delta }\overrightarrow{m}}{\mathrm{\Delta }}}=\overrightarrow{m}$.

D-2.2.4 Decoding₂

In §D-2.2.1, we already derived the decoding formula that transforms an $(n-1)$-degree polynomial having integer modulo $t$ coefficients into an $n$-dimensional input slot vector as follows:

$\overrightarrow{v}=W^T\cdot \overrightarrow{m}$

D-2.2.5 Summary

However, Summary D-2.2.5 is not the final version of BFV’s batch encoding. In §D-2.9, we will explain how to homomorphically rotate the input vector slots without decrypting the ciphertext that encapsulates it. To support such homomorphic rotation, we will need to slightly update the encoding scheme explained in Summary D-2.2.5. We will explain how to do this in §D-2.9, and BFV’s final encoding scheme is summarized in Summary D-2.9.3 in §D-2.9.3.