# 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  
Here, we are going to show our CP-ABE scheme, which supports the access structure described through the NC\({}^{1}\) circuit. The specific features and construction have been shown in Section 2.1.2. First of all, we give the specific restrictions of each parameter in the scheme according to the proof of correctness and security. The **Setup** algorithm should select the appropriate parameters and noise distributions \(n,m,\sigma,q\) and \(\psi_{l\mathit{mce}},\psi_{1},\psi_{2},\psi_{big}\), which meet the following conditions (fix any \(0<\epsilon<1/2\)):  
* \(\sigma<q,n=f(\lambda),\psi_{l\mathit{mce}}=\hat{\mathcal{D}}_{\mathbb{Z}, \sigma},n\cdot q/\sigma<2^{n^{\varepsilon}}\) (due to the LWE security)
* \(m>t_{max}n\,\log q+\omega(\log n)+\lambda\) (due to the leftover hash lemma)
* \(\sigma\geq O(\sqrt{t_{max}n\log q})\cdot\omega(\sqrt{\log m})+\lambda\) (due to the trapdoor sampling)
* \(\psi_{1}=\hat{\mathcal{D}}_{\mathbb{Z}^{m},\psi_{2}}=\hat{\mathcal{D}}_{ \mathbb{Z}^{m}}\) (due to the trapdoor sampling)
* \(\psi_{big}=\hat{\mathcal{D}}_{\mathbb{Z}^{m},\beta}\), where \(\delta\geq\sigma\sqrt{m}\|R\|\cdot\lambda^{w(1)}\) (due to the smudging/security)
* \(|\,\,\mathrm{U}\mid[\sqrt{2}m^{3/2}\sigma(\sqrt{2\sigma^{2}+2\sigma\delta+ \delta^{2}})+m^{3/2}\sigma\delta]<q/4\) (due to the correctness) **Setup**(1\({}^{\lambda}\)): Take the security parameter \(\lambda\), the maximum width \(t_{max}=t_{max}(\lambda)\) of a linear secret sharing matrix corresponding to the scheme, and the attribute set \(\mathbb{U}\) as inputs and perform the following steps in order:  
* Select an LWE instance with the appropriate parameters \(n,m,q\), as well as the distribution described above. * Select a vector \(\mathbf{x}\leftarrow\mathbb{Z}^{n}_{q}\) and select a series of random matrices \(\{\mathbf{P}_{u}\}_{u\in\mathbb{U}}\) at the same time. * Run algorithm \(\mathbf{TrapGen}(1^{n},1^{m},q)\) to generate \((\mathbf{A}_{u},\mathbf{T}_{\mathbf{A}_{u}})_{u\in\mathbb{U}}\). * Output the public parameters and master secret keys: \[\mathbf{PK}=(n,m,q,\psi_{l\mathit{mce}},\psi_{2},\psi_{big},\mathbf{x},\{ \mathbf{A}_{u}\}_{u\in\mathbb{U}},\{\mathbf{P}_{u}\}_{u\in\mathbb{U}}), \mathbf{MSK}=(\{\mathbf{T}_{\mathbf{A}_{u}}\}_{u\in\mathbb{U}}).\]  
\(\mathbf{KeyGen}(\mathbf{MSK},U)\): With the master secret key and the collection of attributes \(U\in\mathbb{U}\) as inputs, perform the following steps:  
* Sample a \(\hat{\mathbf{w}}\leftarrow\psi_{1}\) and set the vector \(\mathbf{w}=(1,\hat{\mathbf{w}})\in\mathbb{Z}^{m}\). * For each \(u\in U\), sample matrix \(\mathbf{j}_{u}\leftarrow\hat{\mathcal{D}}_{\mathbb{Z}^{m},\beta}\), at the same time, and, finally, let \(\mathbf{z}_{u}=\mathbf{P}_{u}\mathbf{w}-\mathbf{A}_{u}\mathbf{j}_{u}(\mathit{ mod}\,\,q)\). * Sample \(\mathbf{S}_{u}\leftarrow\{-1,1\}^{m\times m}\). * Sample \(\left[ \begin{array}{c}\mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]\leftarrow\mathbf{SampleLeft}(\mathbf{A}_{u}, \mathbf{A}_{u}\mathbf{S}_{u},\mathbf{T}_{\mathbf{A}_{u}},\mathbf{z}_{u})\) for some parameter \(\sigma\). In other words, choose \(\left[ \begin{array}{c}\mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]\) to make the equation \([\mathbf{A}_{u},\mathbf{A}_{u}\mathbf{S}_{u}]\cdot\left[ \begin{array}{c} \mathbf{k}_{u}\\ \mathbf{g}_{u}\end{array} \right]=\mathbf{z}_{u}\) holds. * Let \(\mathbf{h}_{u}=\left[ \begin{array}{c}\mathbf{k}_{u}+\mathbf{j}_{u}\\ \mathbf{g}_{u}\end{array} \right]\) and output \(SK_{f}=(\mathbf{w},\{\mathbf{h}_{u}\}_{u\in U})\). \(\mathbf{Enc}(\mathbf{PK},\mu,(\mathbf{G},\eta))\): With the public parameters PK, a message \(\mu\in\{0,1\}\) needs to be encrypted, and an LSSS access policy \((\mathbf{G},\eta)\), generated from the previous transformation, are the inputs (that is to say, where \(\mathbf{G}=(\mathbf{G}_{i,l})_{y\times l\mathit{mce}}\in\{-1,0,1\}^{y\times l \mathit{mce}}\subset\mathbb{Z}^{y\times l\mathit{mce}}_{q}\)).