## 4 Batched MK-BGV Scheme
### Ciphertext Packing Based on Polynomial CRT  
Recall from Section 3.1 that for a given integer \(p\), the input plaintext in the \(\mathbf{MK-BGV}\) scheme is structured based on the algebraic structure \(R_{p}=R/\left(p\cdot R\right)=\mathbb{Z}_{p}[X]/\left(\Phi_{k}(X)\right)\), where both addition and multiplication are defined modulo \(\Phi_{k}(X)\) and \(p\). Let \(\mathbb{F}_{p}\) represent a finite field with \(p\) as its characteristic. The polynomial \(\Phi_{k}(X)\) can be decomposed modulo \(p\) into \(\xi\) distinct irreducible factors \(f_{i}(X)\), such that \(\Phi_{k}(X)\equiv\prod\limits_{i=0}^{\xi-1}f_{i}(X)\pmod{p}\), where each factor \(f_{i}(X)\) has degree \(d\), with \(d=\varphi(k)/\xi\), and \(p^{d}\equiv 1(\text{mod }k)\). This decomposition enables multiple plaintext values to be mapped into a single plaintext element via the Polynomial CRT, which is then encrypted into a ciphertext supporting slot-wise SIMD operations. We then have the following isomorphism for \(R_{p}\):  
\[R_{p}=\mathbb{Z}_{p}[X]/\left(f_{0}(X)\cdot f_{1}(X)\cdots f_{\xi-1}(X)\right) \cong\mathbb{Z}_{p}[X]/f_{0}(X)\times\cdots\times\mathbb{Z}_{p}[X]/f_{\xi-1}( X)\cong\mathbb{F}_{p^{d}}\times\cdots\times\mathbb{F}_{p^{d}}=\left(\mathbb{F}_{p ^{d}}\right)^{\xi}.\]  
In this representation, \(R_{p}\) is isomorphic to \(\xi\) copies of \(\mathbb{Z}_{p}[X]/f_{0}(X),\ldots,\mathbb{Z}_{p}[X]/f_{\xi-1}(X)\), each corresponding to a message in \(\mathbb{F}_{p^{d}}\). Here, each factor \(\mathbb{Z}_{p}[X]/f_{i}(X)\cong\mathbb{F}_{p^{d}}\) is referred to as a \"plaintext slot\". This allows us to represent \(\xi\) plaintext elements of \(\mathbb{F}_{p^{d}}\) as a single element in \(R_{p}\). By Definition 1, algebraic operations (addition and multiplication) in \(R_{p}\) can be viewed as parallel operations across all slots, where each slot corresponds to a separate message. This enables us to perform homomorphic computations on \(\xi\) input values simultaneously, which forms the foundation for efficient batch homomorphic computations. The above isomorphisms are explicitly manifested through the following mappings \(\mathcal{F}\) and \(\mathcal{G}\):  
\[\mathcal{F}:\left\{ \begin{array}{l}\mathbb{R}_{p^{d}}^{\xi}\longrightarrow \mathbb{Z}_{p}[X]/f_{0}(X)\times\cdots\times\mathbb{Z}_{p}[X]/f_{\xi-1}(X)\\ \left(m_{0},\ldots,m_{\xi-1}\right)\longmapsto\left(\mathcal{F}_{0}(m_{0}), \ldots,\mathcal{F}_{\xi-1}\left(m_{\xi-1}\right)\right)\end{array} \right.,\]  
\[\mathcal{G}:\left\{ \begin{array}{l}\mathbb{Z}_{p}[X]/f_{0}(X)\times\cdots \times\mathbb{Z}_{p}[X]/f_{\xi-1}(X)\longrightarrow R_{p}\\ \left(\alpha_{0},\ldots,\alpha_{\xi-1}\right)\longmapsto\sum\limits_{i=0}^{ \xi-1}\alpha_{i}(X)\beta_{i}(X)\gamma_{i}(X)\end{array} \right.,\]  
where \(\gamma_{i}(X)=\frac{\Phi_{k}(X)}{f_{i}(X)}\), \(\beta_{i}(X)=\frac{1}{\gamma_{i}(X)}(\text{mod}f_{i}(X))\). Hence, \(PCRT_{p}=\mathcal{F}\circ\mathcal{G}\), where \(\circ\) denotes function composition, forms a mapping that is an isomorphism from \(\mathbb{F}_{p^{d}}^{\xi}\) to \(R_{p}\). Since this mapping is a ring isomorphism, it is bijective and structure-preserving by Definition 1, which guarantees the existence of its inverse mapping \(PCRT_{p}^{-1}\). This inverse uniquely recovers the original slot-wise representation in \(\mathbb{F}_{p^{d}}^{\xi}\) from any ring element in \(R_{p}\), enabling slot-level access and decomposition when needed. Let \(\mathbf{x}=(x_{0},x_{1},\ldots,x_{\xi-1})\in\mathbb{F}_{p^{d}}^{\xi}\) and \(\mathbf{y}=(y_{0},y_{1},\ldots,y_{\xi-1})\in\mathbb{F}_{p^{d}}^{\xi}\) be two plaintext vectors consisting of \(\xi\) independent slots, where each component \(x_{i},y_{i}\in\mathbb{F}_{p^{d}}\) represents one plaintext message. Let \(\hat{x}=PCRT_{p}(\mathbf{x})\in R_{p}\) and \(\hat{y}=PCRT_{p}(\mathbf{y})\in R_{p}\) be their encoded representations in the plaintext ring \(R_{p}=\mathbb{Z}_{p}[X]/(\Phi_{k}(X))\) via the Polynomial CRT-based packing.