# A CP-ABE Scheme Based on Lattice LWE and Its Security Analysis
## 2 Relevant Basic Knowledge
### The Relevant Knowledge of Lattice  
Here, we will give some lattice-related knowledge used in our CP-ABE construction. All of the relevant contents are adapted from the corresponding references. In order to save space, only an overview of lattice and Gaussian distributions is given here. For more details, please refer to [24]. A lattice whose dimension is \(m\) is a discrete additive subgroup of \(\mathbb{R}^{m}\). For a matrix \(\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}\), where \(n,m\), and \(q\) are integers greater than \(0\), \(\Lambda_{q}^{\perp}(\mathbf{A})=\{\mathbf{y}\in\mathbb{Z}^{m}\mid\mathbf{Ay}= \mathbf{0}(\mathit{mod}\ q)\}\) and \(\Lambda_{q}^{\mathbf{u}}(\mathbf{A})=\{\mathbf{y}\in\mathbb{Z}^{m}\mid \mathbf{Ay}=\mathbf{u}(\mathit{mod}\ q)\}\) are defined. Assume that \(\sigma\) is an arbitrary real number greater than \(0\). The Gaussian distribution is a distribution interpreted by a probability distribution function \(\rho(\mathbf{y})=exp(-\pi\|\mathbf{y}-\mathbf{c}\|/\sigma^{2})\) (where \(\mathbf{c}\in\mathbb{Z}^{n}\)), if a discrete set \(V\subseteq\mathbb{R}^{m}\) is involved, then \(\rho_{\sigma,\mathbf{c}}(V)=\sum_{\mathbf{y}\in V}\rho_{\sigma,\mathbf{c}}( \mathbf{y})\), and then \(\rho_{V,\sigma,\mathbf{c}}(\mathbf{y})=\rho_{\sigma,\mathbf{c}}(\mathbf{y})/ \rho_{\sigma,\mathbf{c}}(V)\) is defined as a Gaussian distribution whose parameter is \(\sigma\) on the set \(V\), represented by the symbol \(\mathcal{D}_{V,\sigma}\). We use \(\tilde{\mathcal{D}}_{V,\sigma}\) to represent the truncated Gaussian distribution, which is statistically indistinguishable from the Gaussian distribution \(\mathcal{D}_{V,\sigma}\). The \(\tilde{\mathcal{D}}_{V,\sigma}\) is the same as the \(\mathcal{D}_{V,\sigma}\) except that when the \(l_{\infty}\) norm exceeds \(\sqrt{m}\sigma\), it will output \(0\). **Definition 6** (Decisional Lw [10]). : _Select a \(\lambda\) as the security parameter, then let \(n\), \(m\), and \(q\) be functions of \(\lambda\) and positive integers at the same time. Therefore, suppose there is a probability distribution \(\psi=\psi(\lambda)\) (in general, \(\psi\) is a distribution \(\mathcal{D}_{\mathbb{Z},\text{aq}}\) with the condition that \(\alpha<1\)) over \(\mathbb{Z}\). The DLWE\({}_{n,m,q,\psi}\) problem declares that for any \(m=\text{poly}(n)\), in the case of \(\mathbf{A}\leftarrow\mathbb{Z}_{q}^{n\times m},\mathbf{s}\leftarrow\mathbb{Z}_ {q}^{n},\mathbf{u}\leftarrow\mathbb{Z}_{q}^{n}\), and \(\mathbf{e}\leftarrow\psi^{m}\), there will be a pair of distributions that are computationally indistinguishable as shown below:_  
\[(\mathbf{A},\mathbf{s}^{\top}\mathbf{A}+\mathbf{e}^{\top})\stackrel{{ \mathfrak{c}}}{{\approx}}(\mathbf{A},\mathbf{u}^{\top}).\]  
**Lemma 1** (**Leftover Hash Lemma [25]**). : _Let \(n\) and \(q\) be two functions from \(\mathbb{N}\) to \(\mathbb{N}\). Therefore, let \(m>(n+1)\log q+w(\log n)\) and \(l=l(n)\) be a function of \(n\). Then, there are the two distributions shown below are statistically indistinguishable:_  
\[\mathcal{D}_{1} \equiv\{(\mathbf{B},\mathbf{BS})\ |\ \mathbf{B}\leftarrow\mathbb{Z}_{q} ^{n\times m},\mathbf{S}\leftarrow\{-1,1\}^{m\times l}\}\] \[\mathcal{D}_{2} \equiv\{(\mathbf{B},\mathbf{R})\ |\ \mathbf{B}\leftarrow\mathbb{Z}_{q} ^{n\times m},\mathbf{R}\leftarrow\mathbb{Z}_{q}^{n\times l}\}\]  
**Lemma 2** (**Smudging [24]**). : _Suppose \(n\) belongs to \(\mathbb{N}\). For arbitrary \(\mathbf{c}\in\mathbb{Z}^{n}\) and arbitrary real \(\delta\geq\omega(\sqrt{\log n})\), there is always \(SD(\mathcal{D}_{\mathbb{Z}_{n,\delta}},\mathcal{D}_{\mathbb{Z}_{n,\delta, \mathbf{c}}})\leq\|\mathbf{c}\|/\delta\)._  
**Lemma 3** (**Lattice Trapdoor [25]**). : _A lattice trapdoor sampler is made up of a pair of algorithms, and the specific meaning and features are shown below:_  
1. \(\mathbf{TrapGen}(1^{n},1^{m},q)\mapsto(\mathbf{B},\mathbf{T_{B}})\)_: The purpose of the algorithm is to output a matrix_ \(\mathbf{B}\) _and its corresponding trapdoor_ \(\mathbf{T_{B}}\)_, when the input is the dimension_ \(n,m\) _of the matrix and_ \(q\)_.