# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 2 Preliminaries
### Discrete Gaussian Distribution  
The Gaussian distribution is a commonly used probability distribution in the design of lattice cryptographic schemes. Next, we will introduce the relevant definitions and important lemmas involved in this paper.  
**Definition 9** (Gaussian Function).: _Given any real number \(\sigma\in\mathbb{R}>0\), with standard deviation \(\sigma\) and a center \(\sigma\in\mathbb{R}^{n}\), the Gaussian function for all \(\forall\mathbf{x}\in\mathbb{R}^{n}\) is defined as follows:_  
\[\rho_{\sigma,\sigma}(\mathbf{x})=exp\left(\frac{-\pi\|\;\mathbf{x}-c\;\|^{2}} {\sigma^{2}}\right)\]  
**Definition 10** (Discrete Gaussian Distribution).: _Consider \(\Lambda\in\mathbb{R}^{m\times n}\). Given a real number \(\sigma\in\mathbb{R}>0\), and a center \(c\in\mathbb{R}^{n}\) with standard deviation \(\sigma\), the discrete Gaussian distribution for any \(\forall\mathbf{x}\in\Lambda\) is defined as follows:_  
\[\mathcal{D}_{\Lambda,\sigma,\varepsilon}(\mathbf{x})=\frac{\rho_{\sigma, \varepsilon}(\mathbf{x})}{\rho_{\sigma,\varepsilon}(\Lambda)}=\frac{\rho_{ \sigma,\varepsilon}(\mathbf{x})}{\sum_{\mathbf{v}\in\Lambda}\rho_{\sigma, \varepsilon}(\mathbf{v})}\]  
_For clarity, when \(c=0\), \(\rho_{\sigma,0}\) and \(\mathcal{D}_{\Lambda,\sigma,0}\) are simplified to \(\rho_{\sigma}\) and \(\mathcal{D}_{\Lambda,\sigma}\), respectively. Similarly, when \(\sigma=1\), \(\rho_{1}\) is denoted as \(\rho\). The distribution \(\mathcal{D}_{\Lambda,\sigma,\varepsilon}\) is generally defined over the lattice \(\Lambda=\Lambda_{q}^{\perp}(\mathbf{A})\) associated with a matrix \(\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}\), or over a shifted lattice \(\Lambda=\mathbf{t}+\Lambda_{q}^{\perp}(\mathbf{A})\), where \(\mathbf{t}\in\mathbb{Z}^{m}\)._  
**Lemma 1** ([24]).: _Consider \(\mathbf{B}\) be a basis for the m-dimensional lattice \(\Lambda\), and for some negligible function \(\in m\), let \(s\geqslant\eta_{\in}(\Lambda)\). Then,_  
\[\Pr_{\mathbf{x}\leftarrow\mathcal{D}_{\Lambda,s}}\left[\|\mathbf{x}\|>s\sqrt{ m}\right]\leq\text{negl}(m)\]  
**Lemma 2** ([25]).: _Let \(n\) be a positive integer, and let \(\mathbf{t}\) be a vector randomly selected from \(\mathbb{Z}^{m}\). Let the error vector \(\mathbf{y}\overset{\overset{\rightarrow}{\mathbf{y}}}{\overset{\rightarrow}{ \mathbf{x}}}\mathbb{Z}_{q}^{m}\), where \(0<\alpha\leq\left(\omega\big{(}\sqrt{\log n}\big{)}\right)^{-1}\), and \(\overset{\rightarrow}{\mathbf{y}}_{\alpha}\) represents the discrete Gaussian distribution over \(\mathbb{Z}_{q}\) corresponding to a normal distribution with mean 0 and standard deviation \(\frac{\alpha}{\sqrt{2\pi}}\) over \([0,1)\). If \(\overset{\rightarrow}{\mathbf{y}}_{\alpha}\) represents an m-dimensional error vector randomly selected from the distribution \(\overset{\rightarrow}{\mathbf{y}}_{\alpha}\), then \(\big{|}\mathbf{t}^{\mathsf{T}}\mathbf{y}\big{|}\) can be viewed as an integer in the range \([0,q-1]\) and satisfies_  
\[\big{|}\mathbf{t}^{\mathsf{T}}\mathbf{y}\big{|}\leq\|\mathbf{t}\|q\alpha \omega\Big{(}\sqrt{\log m}\Big{)}+\frac{\|\mathbf{t}\|\sqrt{m}}{2}\]  
**Lemma 3** ([26]).: _Assume \(m>(n+1)\log q+\omega\log n\), and \(q\) is a prime. Uniformly randomly select matrices \(\mathbf{A}\in\mathbb{Z}_{q}^{m\times n}\) and \(B\in\mathbb{Z}_{q}^{m\times n}\). Let \(\mathbf{R}\) be an \(m\times n\) matrix uniformly randomly selectedfrom \(\{0,1\}^{m\times m}\). For all vectors \(w\in\mathbb{Z}_{q}^{m}\), The distributions \(\big{(}\mathbf{A},\mathbf{AR},\mathbf{AR}^{\mathbf{T}}\mathbf{w}\big{)}\) and \(\big{(}\mathbf{A},\mathbf{B},\mathbf{R}^{\mathbf{T}}\mathbf{w}\big{)}\) are statistically indistinguishable._