# 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 \(\|p_{\mathcal{A}\mathcal{I}}(\lambda)-p_{\mathcal{A}\mathcal{B}}(\lambda)\| \leq negl_{8}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 9**: This is similar to Algorithm 9, except for the part marked with wireframes in Algorithm 10. Namely, the way to generate the matrices \(\{A_{u}\}_{u\in\rho([y])}\) has been replaced. The indistinguishability of Algorithm 1 and Algorithm 2 is derived from the excellent characteristics of the trapdoor sampling of lattice as described earlier. So, there is obviously \(\|\beta_{\mathcal{A}\mathcal{B}}(\lambda)-\beta_{\mathcal{A}\mathcal{B}}( \lambda)\|\leq negl_{9}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 10**: This is similar to Algorithm 10, except for the two parts marked with wireframes in Algorithm 11. Namely, the way to generate the vectors \(\mathbf{\hat{e}}_{i}\) in the \(\{\mathbf{\hat{e}}_{i}\}_{i\in[y]}\) has been replaced. The indistinguishability of Algorithm 10 and Algorithm 11 is derived from the smudging lemma (Lemma 2). So, there is obviously \(\|\beta_{\mathcal{A}\mathcal{B}}(\lambda)-\beta_{\mathcal{A}\mathcal{1}0}( \lambda)\|\leq y\cdot m\cdot negl_{sum}\leq negl_{10}(\lambda)\) for all adversaries \(\mathcal{A}\). **Hybrid 11**: This is basically the same as Algorithm 11, except for a few framed parts, which are summarized as different ways of generating ciphertext in the challenge phase. In Algorithm 11, \(\{\mathbf{c}_{i}\}_{i\in[y]}\) resembles a set of \(\text{LWE}_{n,q,\sigma}\) samples, and, here, we really want to use LWE to hide \(s\). Assume that for any \(i\in[y]\), \([\mathbf{A}_{u},\mathbf{A}_{u}\mathbf{S}_{u}]=[\mathbf{a}_{1},\dots,\mathbf{a}_{m},\mathbf{a}_{m+1}, \dots,\mathbf{a}_{2m}]\), then \(\mathbf{c}_{i}=\mathbf{s}[\mathbf{A}_{u},\mathbf{A}_{u}\mathbf{S}_{u}]+\mathbf{e}_{i}^{\top}=\mathbf{s}[\bm {a}_{1},\dots,\mathbf{a}_{m},\mathbf{a}_{m+1},\dots,\mathbf{a}_{2m}]+\mathbf{e}_{i}^{\top}=[\bm {s}\mathbf{a}_{1}+\mathbf{e}_{i,1},\dots,\mathbf{s}\mathbf{a}_{m}+\mathbf{e}_{i,m+1}+\mathbf{e}_{i,m+1}, \dots,\mathbf{s}\mathbf{a}_{2m}+\mathbf{e}_{i,2m}]\). Because of the decisional LWE, we have that the selection of \(\{\mathbf{c}_{i}\}_{i\in[y]}\) in Algorithm 11 and Algorithm 12 is indistinguishable. In addition, Algorithm 12 makes a semantic transformation with \(\mathbf{\hat{v}}_{l}=\mathbf{s}+\mathbf{v}_{l}^{\prime}\) so that \(\{\mathbf{\hat{c}}_{i}\}_{i\in[y]}\) gets rid of \(s\) and has the same distribution as the selection in Algorithm 11. In turn, if we look at \(\mathbf{s}\mathbf{x}^{\top}\), because of \(\mathbf{x}\leftarrow\mathbb{Z}_{q}^{n}\), we can make \(\mathbf{a}_{2m+1}=\mathbf{x}\) and randomly select \(\mathbf{e}_{2m+1}\leftarrow\mathcal{D}_{\mathcal{Z},\sigma}\). Then, there must be \(\text{MSB}(\mathbf{s}\mathbf{x}^{\top})=\text{MSB}(\mathbf{s}\mathbf{x}^{\top}+\mathbf{e}_{2m+1})\). Then, according to the decisional \(\text{LWE}_{n,\sigma}\), we have that the distribution of \(\text{MSB}(\mathbf{s}\mathbf{x}^{\top})\) is indistinguishable from that of \(\text{MSB}(\tau)\) (where \(\tau\leftarrow\mathbb{Z}_{q}\)). To sum up, the indistinguishability of Algorithm 11 and Algorithm 12 is derived from the LWE assumption. So, there is obviously \(\|\beta_{\mathcal{A},10}(\lambda)-\beta_{\mathcal{A},11}(\lambda)\|\leq negl_ {11}(\lambda)\) for all adversaries \(\mathcal{A}\). ```








### Comparison

For a long time before, the only known way to implement an LWE-based CP-ABE scheme was to convert a circuit-based KP-ABE scheme into a CP-ABE scheme, in which the access policies and sets of attributes were represented as circuits by using general circuits. However, this transformation essentially results in a CP-ABE with restricted access policy classes, whose parameters are far from ideal. In recent years, people have tried to make some improvements to the CP-ABE based on the general-purpose circuits described above, while trying to get rid of other assumptions, and have wanted to design solutions only based on LWE.