# A CP-ABE Scheme Based on Lattice LWE and Its Security Analysis
## 3 Our Ciphertext-Policy ABE Scheme for NC\({}^{1}\) Circuits Based on LWE
### Security Analysis
So, there is obviously \(\|\beta_{\mathcal{A}\mathcal{2}}(\lambda)-\beta_{\mathcal{A}\mathcal{3}}( \lambda)\|\leq negl_{3}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 4**: This is similar to Algorithm 4, except for those parts marked with a wire-frame in Algorithm 5. It chooses another indistinguishable way to generate \(\{\mathbf{D}_{j}\}_{j\in(2\ldots,n\sigma)}\), which stems from the trapdoor lattice sampler. So, there is obviously \(\|\beta_{\mathcal{A}\mathcal{3}}(\lambda)-\beta_{\mathcal{A}\mathcal{A}}( \lambda)\|\leq negl_{4}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 5**: This is similar to Algorithm 5, except for several parts marked with wire-frames in Algorithm 6, which can be summarized as the way in which \(\left[ \begin{array}{c}\mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]\) is generated when answering the private key query of the adversary \(\mathcal{A}\) for all \(u\in U\cap\eta(y)\). This indistinguishably stems from the smudging lemma (Lemma 2), so we can deduce that \(\|\beta_{\mathcal{A}\mathcal{A}}(\lambda)-\beta_{\mathcal{A}\mathcal{5}}( \lambda)\ \mid\leq Q_{key}(\lambda)\cdot\ \mid U\cap\eta(y)\mid \cdot 2m\cdot negl_{sum}(\lambda)\leq negl_{5}(\lambda)\) for all adversaries \(\mathcal{A}\) where \(negl_{sum}\) is a negligible function to measure the indistinguishability of two distributions under smudging and \(Q_{key}\) represents the number of private key queries made. For example, for all of the \(m\in\mathbb{N}\) and \(\lambda\in\mathbb{N}\), when \(\mathcal{F}_{1}\equiv\{\mathbf{k}_{1}\mid\mathbf{k}_{1}\leftarrow\mathcal{D}_{ \mathbb{Z}^{m},\beta}\}\), \(\mathcal{F}_{2}\equiv\{\mathbf{k}_{1}+\mathbf{k}_{2}\mid\mathbf{k}_{1} \leftarrow\mathcal{D}_{\mathbb{Z}^{m},\beta},\mathbf{k}_{2}\gets\mathcal{D }_{\mathbb{Z}^{m},\rho}\}\), there is \(\mathrm{SD}(\mathcal{F}_{1},\mathcal{F}_{2})\leq m\cdot negl_{sum}(\lambda)\) (where \(\delta\geq\sigma\sqrt{m}\|R\|\cdot\lambda^{n(1)}\)). **Hybrid 6**: It is basically similar to Algorithm 6, just except the generation method of the vector \(\mathbf{t}\) is different when answering the adversary \(\mathcal{A}\). Here, in order to achieve the same purpose, we use the idea of Hybrid 6 in [20]. Namely, let \(\mathbf{b}=(b_{1},\ldots,b_{t_{max}})\) be a vector such that \(b_{1}=1\) and \(\sum_{l\in(2\ldots,t_{max})}\mathbf{G}_{\eta^{-1}(u)}b_{l}=0\) for all \(u\in U\). Note that by the game restriction, the set of rows of \(G\) with indices in \(\eta^{-1}(U)\) must be unauthorized with respect to the access policy \((G,\eta)\), and, hence, the existence of such a vector \(\mathbf{b}\) is guaranteed. We can find that the indistinguishability of Algorithm 6 and Algorithm 7 comes from the excellent characteristics of the trapdoor sampling of lattice. So, there is obviously \(\|\beta_{\mathcal{A}\mathcal{S}}(\lambda)-\beta_{\mathcal{A}\mathcal{B}}( \lambda)\|\leq negl_{6}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 7**: This is similar to Algorithm 7, except for several parts marked with wire-frames in Algorithm 8. Similar to the methods and goals of Hybrid 7 in [24], here, due to the restrictions of the game, for each secret key query of \(\mathcal{A}\) corresponding to some attribute set \(U\subset\mathbb{U}\), the rows of \(\mathbf{G}\) with indices in \(\eta U\) are linearly independent. These changes can also be seen as a simple semantic, so they are indistinguishable; therefore, there is obviously \(\|p_{\mathcal{A}\mathcal{B}}(\lambda)-p_{\mathcal{A}\mathcal{I}}(\lambda)\| \leq negl_{7}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 8**: This is similar to Algorithm 8, except for several parts marked with wire-frames in Algorithm 9, which can be summarized as the way in which \(\left[ \begin{array}{c}\mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]_{u\in U\cap\rho([y])}\) is generated when answering the private key query of the adversary \(\mathcal{A}\). The indistinguishability of Algorithm 8 and Algorithm 9 is derived from the excellent characteristics of the trapdoor sampling of lattice.