# 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  
In this part, we will give the security analysis of the scheme in detail. The security proof of our scheme is carried out strictly according to the idea of the security proof in [20]. Theorem 1 ([20]): _Under the condition that the LWE hypothesis is true, the CP-ABE scheme we present for all access structures described through NC\({}^{1}\) circuits is selectively secure._  
Theorem 2: _Under the condition that the LWE assumption is true, the CP-ABE scheme we present is selectively secure under linear independence restriction._  
Proof: To prove the correctness of Theorem 2, we considered a series of hybrid games, which are slightly different from each other. The first hybrid game matches the real choice security game under the linear independent restriction, and the final hybrid scheme is the one in which the advantage of the opponent is zero. By demonstrating that the advantages of the adversaries have only a completely negligible change between different consecutive hybrid games, we have finally proved the correctness of Theorem 2. Next, we will talk about the specific hybridization and analysis process. In order to facilitate the explanation, we first use 12 algorithm graphs to show, in detail, the process of 12 hybridizations in which all the symbols used are as defined above. Secondly, we analyze the indistinguishability of any two adjacent hybridization processes in detail. For convenience, we introduce a probability function \(\beta_{\mathcal{A},\mathcal{A}}(\lambda):\mathbb{N}\rightarrow[0,1]\) for all adversaries \(\mathcal{A}\), and any \(x\in\{0,1,\ldots,11\}\) whose input is \(1^{\lambda}\) and output is the probability of the opponent \(\mathcal{A}\) correctly guesses the challenge bit \(b\in\{0,1\}\) in each hybrid program. According to the definition of Algorithm 1, it is known that \(\mid\beta_{\mathcal{A},0}(\lambda)-1/2\mid=Adv_{\mathcal{A}}^{\text{Sel}}(\lambda)\) for all \(\lambda\in\mathbb{N}\). Furthermore, since the generated challenge ciphertext in Algorithm 12 does not disclose any information about the selection of challenge bits, it is known that \(\beta_{\mathcal{A},11}=1/2\) for all \(\lambda\in\mathbb{N}\). Therefore, through the following series of analysis, we can conclude that for all \(\lambda\in\mathbb{N}\), there is obviously  
\[Adv_{\mathcal{A}}^{\text{Sel}}(\lambda)\leq\sum_{x\in[11]}\mid\beta_{ \mathcal{A},\mathcal{A}-1}(\lambda)-\beta_{\mathcal{A},\mathcal{A}}(\lambda) \mid\leq negl(\lambda) \tag{2}\]  
**Hybrid 0**: This is the original selective weak security model of the CP-ABE scheme we constructed. **Hybrid 1**: This is similar to Algorithm 1, except for the three parts marked with a wireframe in Algorithm 2, and these changes are only semantic (As in Algorithm 1, \(\{\mathbf{v}_{l}\}_{l\in\{2,\ldots,l_{max}\}}\leftarrow\mathbb{Z}_{q}^{m}\), Algorithm 2 replaces the original vector \(\{\mathbf{v}_{l}\}_{l\in\{2\)\(\ldots,l_{max}\}}\) with \(\hat{\mathbf{v}}_{l}^{\top}\mathbf{D}_{l}\), where \(\{\hat{\mathbf{v}}_{l}\}_{l\in\{2,\ldots,l_{max}\}}\leftarrow\mathbb{Z}_{q}^{n}\) and \(\{\mathbf{D}_{l}\}_{l\in\{2,\ldots,l_{max}\}}\leftarrow\mathbb{Z}_{q}^{n\times m}\). The semantic changes involved later are also similar to the methods here), so there is obviously \(\beta_{\mathcal{A},0}(\lambda)=\beta_{\mathcal{A},1}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 2**: This is similar to Algorithm 2, except for the two parts marked with a wireframe in Algorithm 3, and these changes are only semantic, so there is obviously \(\beta_{\mathcal{A},1}(\lambda)=\beta_{\mathcal{A},2}(\lambda)\) for all adversary \(\mathcal{A}\). **Hybrid 3**: This is similar to Algorithm 3, except for those parts marked with a wire-frame in Algorithm 4. The indistinguishability of Algorithm 3 and Algorithm 4 stems from the leftover hash lemma (as shown in Lemma 1) and the basic fact that the sum of two random matrices is still a random matrix.