# 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
### Correctness  
Next, we will prove the correctness of the scheme. Given an attribute collection \(U\subset\mathbb{U}\) and an arbitrary access policy \((\mathbf{G},\eta)\), where \(U\) forms an authorized set, calculate the following equation  
\[Y^{\prime}=\sum_{i\in\Delta}\xi_{i}(\mathbf{c}_{i}^{\top}\mathbf{h}_{u}+\hat{ \mathbf{c}}_{i}^{\top}\mathbf{w}).\]  
By substituting the specific values of \(\{\mathbf{c}_{i}\}_{i\in[y]}\) and \(\{\hat{\mathbf{c}}_{i}\}_{i\in[y]}\) into the above formula, we can obtain  
\[Y^{\prime}=\sum_{i\in\Delta}\xi_{i}\mathbf{s}^{\top}[\mathbf{A} _{\eta(i)}\|\mathbf{A}_{\eta(i)}\mathbf{S}_{\eta(i)}]\mathbf{h}_{\eta(i)}+\sum _{i\in\Delta}\xi_{i}(\mathbf{s}^{\top}\mathbf{x},0,\ldots,0)\mathbf{w}+\] \[\sum_{i\in\Delta J\in\{2,\ldots,t_{max}\}}\xi_{i}G_{i,j}\mathbf{v }_{i}^{\top}\mathbf{w}-\sum_{i\in\Delta}\tilde{\xi}_{i}\mathbf{s}^{\top} \mathbf{P}_{\eta(i)}\mathbf{w}+\sum_{i\in\Delta}\tilde{\xi}_{i}\mathbf{e}_{i} \mathbf{h}_{\eta(i)}+\sum_{i\in\Delta}\tilde{\xi}_{i}\hat{\mathbf{e}}_{i} \mathbf{w}.\]  
Here, let us review the previous key generation process. For each \(u\in U\), \(\mathbf{h}_{u}=\left[ \begin{array}{c}\mathbf{k}_{u}+\mathbf{j}_{u}\\ \mathbf{g}_{u}\end{array} \right]\), and \([\mathbf{A}_{u}\|\mathbf{A}_{u}\mathbf{S}_{u}]\cdot\left[ \begin{array}{c} \mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]=\mathbf{P}_{u}\mathbf{w}-\mathbf{A}_{u} \mathbf{j}_{u}\) is established. That is to say, it holds that  
\[[\mathbf{A}_{\eta(i)}\|\mathbf{A}_{\eta(i)}\mathbf{S}_{\eta(i)}]\mathbf{h}_{ \eta(i)}=\mathbf{P}_{\eta(i)}\mathbf{w}.\]  
Further, there will be  
\[Y^{\prime}= \sum_{i\in\Delta}\xi_{i}\mathbf{s}^{\top}\mathbf{P}_{\eta(i)} \mathbf{w}+\sum_{i\in\Delta}\xi_{i}\mathbf{G}_{i,1}(\mathbf{s}^{\top}\mathbf{ x},0,\ldots,0)\mathbf{w}\] \[+ \sum_{i\in\Delta J\in\{2,\ldots,t_{max}\}}\xi_{i}\mathbf{G}_{i,j} \mathbf{v}_{i}^{\top}\mathbf{w}-\sum_{i\in\Delta}\xi_{i}\mathbf{s}^{\top} \mathbf{P}_{\eta(i)}\mathbf{w}+\sum_{i\in\Delta}\xi_{i}\mathbf{e}_{i}^{\top} \mathbf{h}_{\eta(i)}+\sum_{i\in\Delta}\xi_{i}\hat{\mathbf{e}}_{i}^{\top} \mathbf{w}\] \[= \sum_{i\in\Delta}\xi_{i}\mathbf{G}_{i,1}(\mathbf{s}^{\top} \mathbf{x},0,\ldots,0)\mathbf{w}+\sum_{i\in\Delta J\in\{2,\ldots,t_{max}\}} \xi_{i}\mathbf{G}_{i,j}\mathbf{v}_{i}^{\top}\mathbf{w}+\sum_{i\in\Delta}\xi_{i }\mathbf{e}_{i}^{\top}\mathbf{h}_{\eta(i)}+\sum_{i\in\Delta}\xi_{i}\hat{ \mathbf{e}}_{i}^{\top}\mathbf{w}\] \[= (\sum_{i\in\Delta}\xi_{i}\mathbf{G}_{i,1})(\mathbf{s}^{\top} \mathbf{x},0,\ldots,0)\mathbf{w}+\sum_{l\in\{2,\ldots,t_{max}\}}(\sum_{i\in \Delta}\xi_{i}\mathbf{G}_{i,l})\mathbf{v}_{l}^{\top}\mathbf{w}+\sum_{i\in \Delta}\xi_{i}\mathbf{e}_{i}^{\top}\mathbf{h}_{\eta(i)}+\] \[\sum_{i\in\Delta}\xi_{i}\hat{\mathbf{e}}_{i}^{\top}\mathbf{w}.\]  
According to the above description, the formula \(\sum_{i\in\Delta}\xi_{i}\mathbf{G}_{i,1}=1\) holds. Moreover, for \(1<l\leq t_{max}\), \(\sum_{i\in\Delta}\xi_{i}\mathbf{G}_{i,l}=0\). Additionally, because of \(\mathbf{w}=(1,\hat{\mathbf{w}})\), then calculate \((\mathbf{s}^{\top}\mathbf{x},0,\ldots,0)\mathbf{w}=\mathbf{s}^{\top}\mathbf{x}\). Thus,  
\[Y^{\prime}=\mathbf{s}^{\top}\mathbf{x}+\sum_{i\in\Delta}\tilde{\xi}_{i}\mathbf{ e}_{i}^{\top}\mathbf{h}_{\eta(i)}+\sum_{i\in\Delta}\xi_{i}\hat{\mathbf{e}}_{i}^{ \top}\mathbf{w}.\]  
The correctness is based on the fact that the last two terms of the above two equations are very small and will not affect the MSB of \(\mathbf{s}^{\top}\mathbf{x}\). In order to achieve this, we must make the following inequalities hold with extremely overwhelming probabilities:  
* \(\parallel\mathbf{e}_{i}\parallel\leq\sqrt{2m}\sigma:\) This is because the \(2m\) coordinates of \(\mathbf{e}_{i}\) are selected according \(\hat{\mathcal{D}}_{\mathbb{Z},\sigma}\). * \(\parallel\hat{\mathbf{e}}_{i}\parallel\leq\sqrt{m}\delta:\) The reason for this is precisely because all the coordinates of \(\hat{\mathbf{e}}_{i}\) are selected according to \(\hat{\mathcal{D}}_{\mathbb{Z}^{m},\delta}\), where \(\delta\geq\sigma\sqrt{m}\|R\|\cdot\lambda^{w(1)}\).