# A CP-ABE Scheme Based on Lattice LWE and Its Security Analysis
## 2 Relevant Basic Knowledge
### Linear Secret Sharing Schemes with Linear Independence
#### 2.1.1 Related Contents of LSSS  
A secret sharing scheme means that the secret distributor divides the secret \(d\) into \(n\) parts using a specific algorithm and then distributes \(n\) shares to \(n\) participants. Authorized subsets of \(n\) participants can jointly reconstruct secrets, while other unauthorized subsets cannot. **Definition 1** (Access Structures, [25]). : _A collection \(\mathbb{A}\subseteq 2^{[n]}\backslash\phi\) of non-empty subsets of \(n\) participants labeled from one to \(n\) is called an access structure. The collections that belong to \(\mathbb{A}\) are named the authorized collections, and the collections that do not belong to \(\mathbb{A}\) are named the unauthorized collections. An access structure is deemed monotone in the case that the latter condition is satisfied. That is, for any two \(C,E\in 2^{[n]}\), there is \(E\in\mathbb{A}\) if there are \(C\in\mathbb{A}\) and \(C\subseteq E\)._  
A secret sharing scheme corresponding to a monotone access structure \(\mathbb{A}\) can be regarded as a randomized algorithm whose input is a secret \(d\) and its output is \(n\) parts \(\mathrm{pa}_{1},\ldots,\mathrm{pa}_{n}\). These parts satisfy certain restrictions: that is, \(d\) can be determined by \(\{\mathrm{pa}_{i}\}_{i\in A}\) for arbitrary \(A\in\mathbb{A}\), while other sets are independent of \(d\). A secret sharing scheme corresponding to a non-monotone access structure \(\mathbb{A}\) can be regarded as a randomized algorithm whose input is a secret \(d\), and its output is \(2n\) shares viewed as \(n\) pairs \((\mathrm{pa}_{1,0},\mathrm{pa}_{1,1}),...,(\mathrm{pa}_{n,0},\mathrm{pa}_{n,1})\), these shares satisfy certain restrictions: that is, \(d\) can be determined by \(\{\mathrm{pa}_{i,1}\}_{i\in A}\cup\{\mathrm{pa}_{i,0}\}_{i\
otin A}\) for arbitrary \(A\in\mathbb{A}\), while other sets are independent of \(d\), which can be regarded as a transformation of the above concepts and algorithms. **Definition 2** (Non-monotone LSSS, [25]). : _Let \([n]\) be a group of participants. Additionally, suppose \(q\in\mathbb{N}\) is a prime power. The scheme described above is called non-monotone LSSS \(\Pi\) over \(\mathbb{Z}_{q}\) if the following conditions are true:_  
1. _For_ \(\rho\in\{0,1\}\) _as well as_ \(i\in\{1,\ldots,n\}\)_, each share_ \(\mathrm{pa}_{i,\rho}\) _of a secret_ \(d\in\mathbb{Z}_{q}\) _makes up a vector whose input is over_ \(\mathbb{Z}_{q}\)_._
2. _There must be a share-generating matrix, recorded as_ \(\mathbf{G}\in\mathbb{Z}_{q}^{y\times t}\)_, and there is also a mapping_ \(\eta\) _from_ \([y]\) _to_ \([2n]\)_;_ \(\eta\) _establishes an one-to-one mapping from the rows of_ \(\mathbf{G}\) _to the participants derived from_ \([n]\) _and their corresponding negation (represented by_ \(\{n+1,...,2n\}\)_, respectively). This meets the conditions mentioned later, that is: Given a vector_ \(\mathbf{v}=(d,\alpha_{2},\ldots,\alpha_{t})^{\top}\in\mathbb{Z}_{q}^{t}\)_, then according to_ \(\Pi\)_, for the matrix_ \(\mathbf{G}\) _described above, there must be a vector representation of_ \(y\) _shares of secret_ \(d\) _that is equal to_ \(\mathbf{pa}=\mathbf{G}\cdot\mathbf{v}\in\mathbb{Z}_{q}^{y\times 1}\)_. For_ \(\rho\in\{0,1\}\) _as well as_ \(i\in\{1,\ldots,n\}\)_, the part_ \(\mathrm{pa}_{i,\rho}\) _includes all of the_ \(\mathrm{pa}_{i}\) _values for which_ \(\eta(l)=n(1-\rho)+i\) _(in this way, all \"1 shares\" fall in the first_ \(n\)_, and all \"0 shares\" fall in the last_ \(n\)_). Then,_ \((\mathbf{G},\eta)\) _will be named the LSSS policy about the access structure_ \(\mathbb{A}\)_._  
Based on the analysis of correctness and security in [25], we list the following conclusions. Correctness is achieved through the following condition: if \(R\in[n]\) is authorized, the vector \((1,\underbrace{0,\ldots,0}_{t-1})\in\mathbb{Z}_{q}^{t}\) is in the span of the rows of \(\mathbf{G}_{\widehat{R}}\) (where \(\widehat{R}=R\cup\{i\in\{n+1,\ldots,2n\}\mid i-n\
otin R\}\subset[2n]\)).