# A CP-ABE Scheme Based on Lattice LWE and Its Security Analysis
## 2 Relevant Basic Knowledge
### The Concept of Cp-Abe  
A CP-ABE scheme is defined by four PPT algorithms shown below, which have been adapted from the literature [9]:  
* **Setup** (\(1^{\lambda},1^{\lambda}\)): The setup algorithm is an algorithm whose input is the the security parameter \(\lambda\), which is the input length \(l\) of the function \(f\). Moreover its outputs are a master secret key MSK and a collection of exposed parameters PK. * **Encrypt** (PK, \(\mu\), \(f\)): The encryption program is an algorithm whose inputs are a public key PK, a message \(\mu\), and a function \(f\), and the output is a ciphertext CT.
* **Keygen** (MSK, \(x\)): The keygen algorithm is an algorithm that outputs the private key SK\({}_{x}\) corresponding to the attribute \(x\) with the input of the MSK and the attribute \(x\). * **Decrypt** (PK, SK\({}_{x}\), CT): The decryption program is an algorithm whose input is the public key PK, a secret key SK\({}_{x}\), and a ciphertext CT. If and only if the attribute \(x\) satisfies \(f(x)=1\), it will output the message \(\mu\); otherwise, decryption fails. Definition 3 ([9]): A CP-ABE scheme is correct if the equation shown below holds. Namely,  
\[P_{r} \begin{bmatrix}(\mathrm{PK,MSK})\gets Setup(1^{\lambda},1^{\lambda}) \\ \mu^{\prime}=\mu\mathsf{bigbigbigbigbigbigbig}\begin{matrix}\mathrm{SK}_{x} \gets Keygen(\mathrm{MSK},x)\\ CT\gets Encryption(PK,\mu,f)\\ \mu^{\prime}=\mathbf{Decrypt}(\mathrm{PK},\mathrm{CT},\mathrm{SK})\end{bmatrix} =1- neg(1^{\lambda}).\]  
In fact, CP-ABE schemes that implement the access structure \(\mathbb{A}\) using an LSSS can be seen as an extension of the above definition. Namely, \(f\) is transformed into an access structure over the attribute collection. At the same time, the single attribute \(x\) in the definition above becomes a set \(S\). By the same token, decryption can be successful only when certain conditions are met, that is, the attribute set \(S\) satisfies the access policy \(\mathbb{A}\); otherwise, decryption fails. **Security**: Next, we present the security model of CP-ABE through the game between the challenger and the attacker shown below. **Setup**. _After receiving the security parameters, the adversary submits an access structure \(\mathbb{A}\), and then the challenger runs the setup algorithm and provides the resulting common parameters to the adversary._  
**Phase 1**. _The adversary initiates a polynomial number of private key queries to the challenger, but a limitation of the attribute set is that the access structure \(\mathbb{A}\) must not be met, and the challenger responds and gives the matching private key \(SK\leftarrow\)_**Keygen**_(MSK, \(R\))._  
**Challenge**. _The adversary provides two messages of equal lengths to the challenger, and then the challenger chooses a bit \(b\in\{0,1\}\) with the probability of throwing coins at random and returns the ciphertext \(CT\leftarrow\)_**Encrypt**_(PK, \(\mu_{b}\), \(\mathbb{A}\)) to the adversary._  
**Phase 2**. _This step is equivalent to the repetition of Phase 1._  
**Guess**. _At the end of the game the adversary outputs a guess \(b^{\prime}\) about \(b\)._  
_The probability advantage of an adversary \(\mathcal{A}\) in the above game is defined as:_  
\[\mathrm{Adv}_{\mathcal{A}}^{\mathrm{Sel}}(\lambda)=\mid\Pr[b=b^{\prime}]-1/2 \mid. \tag{1}\]  
**Definition 4** ([20]). : _If for an arbitrary PPT adversary \(\mathcal{A}\) and all \(\lambda\in\mathbb{N}\), there exists a negligible function \(\mathrm{negl}(\cdot)\) such that \(\mathrm{Adv}_{\mathcal{A}}^{\mathrm{Sel}}\leq\mathrm{negl}(\cdot)\) holds, then we call the CP-ABE scheme for LSSS-realizable access structures selectively secure._  
**Definition 5** ([20]). : _If a relaxed setting is made for the key query phase of the above scheme, that is, the rows in the generating matrix \(\mathbf{G}\) corresponding to the attribute set sent by the adversary each key query must be linearly independent, namely, those attribute sets that do not meet the access policy are queried.