## 3 Construction
### Implementation
: Sending \(g,g_{3},X\) to \(\mathcal{B}\), \(\mathcal{B}\) will simulate \(Game_{Real}\) or \(Game_{0}\) with adversary \(\mathcal{A}\); \(\mathcal{B}\) randomly selects \(\alpha,a,\beta\in\mathbb{Z}_{N}\), and selects a random exponent \(u_{i}\in\mathbb{Z}_{N}\) for each attribute in the system, then randomly selects two safe large prime numbers \(p,q\) such that \(gcd(pq,\)\((p-1)(q-1))=1\), calculates \(n=pq,\lambda=lcm(p-1,q-1)\), then randomly selects a positive integer \(g_{1}\) less than \(n^{2}\), and \(\mu=(L(g^{\lambda}modn^{2}))^{-1}mod\ n\), the public parameter

\[\overline{CT_{A,T}}=<\overline{C_{0}}=G_{T}(H(M))\cdot e(g,g)^{as},C_{1}=g^{sT},C_{i,1}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}\mathcal{U}_{\rho(i)}^{-r_{i}},C_{i,2}=g^{s_{1}},C_{i,3}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}>\]7

and public key

\[\overline{CT_{A,T}}=<\overline{C_{0}}=G_{T}(H(M))\cdot e(g,g)^{as},C_{1}=g^{sT},C_{i,1}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}\mathcal{U}_{\rho(i)}^{-r_{i}},C_{i,2}=g^{s_{1}},C_{i,3}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}>\]8

are sent to \(\mathcal{A}\). Next, \(\mathcal{A}\) sends two equal-length messages \(M_{0},M_{1}\), \(T\) generated by his own unique identity and a shared generator matrix \((A^{*},\rho)\) to \(\mathcal{B}\), \(\mathcal{B}\) implicitly sets \(g^{sT}\) to the part of \(G_{p_{1}}\) (and possibly \(G_{p_{1}p_{2}}\) element). Then, \(\mathcal{B}\) flips a coin and pick \(\sigma\in\{0,1\}\) and sets:

\[\overline{CT_{A,T}}=<\overline{C_{0}}=G_{T}(H(M))\cdot e(g,g)^{as},C_{1}=g^{sT},C_{i,1}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}\mathcal{U}_{\rho(i)}^{-r_{i}},C_{i,2}=g^{s_{1}},C_{i,3}=g^{sT}\overline{TA_{i}\cdot\mathbf{v}}>\]9

then randomly selects \(y^{{}^{\prime}}_{2},\ldots,y^{{}^{\prime}}_{n}\), \(r^{{}^{\prime}}_{i}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{N}\), sets the vector \(\mathbf{v}^{{}^{\prime}}=(1,y^{{}^{\prime}}_{2},\ldots,y^{{}^{\prime}}_{n})\), then sets \(C_{i,1}=X^{\sigma TA_{i}}\), \(\mathbf{v}^{{}^{\prime}}X^{-r^{{}^{\prime}}_{i}p_{(i)}}\), \(C_{i,2}=X^{r^{{}^{\prime}}_{i}}C_{i,3}=X^{\beta TA_{i}}\mathbf{v}^{{}^{\prime}}\). We implicitly set \(\mathbf{v}\) to \((s,y^{{}^{\prime}}_{1},\ldots,y^{{}^{\prime}}_{n})\), \(r_{i}=s^{{}^{\prime}}_{i}\), so when \(X\in G_{p_{1}}\), it is a correctly distributed normal ciphertext. If \(X\in G_{p_{1}p_{2}}\), let \(g^{{}^{\prime}}_{2}\) be the \(G_{p_{2}}\) part of \(X\) ( \(X=g^{\epsilon}g^{{}^{\prime}}_{2}\)), so \(C_{1}=g^{\epsilon T}g^{{}^{\prime}T}_{2},C_{2}=g^{\epsilon gT}g^{{}^{\prime}T} _{2},C_{i,1}=g^{\epsilon sTA_{i}\cdot\mathbf{v}^{{}^{\prime}}}g^{-s^{\prime} _{i}u_{p(i)}}\cdot g^{{}^{\prime}aTA_{i}\cdot\mathbf{v}^{{}^{\prime}}-f^{{}^{ \prime}}_{i}u_{p(i)}}\), \(C_{i,2}=g^{s^{\prime}}_{i}g^{{}^{\prime}T}_{2},C_{i,3}=g^{\epsilon STA_{i}\mathbf{v }^{{}^{\prime}}}g^{{}^{\prime}f^{{}^{\prime}}_{2}

Assumptions 2 and 3 can be proved by similar constructions above; see [PERSON]'s scheme [33] for details. ### Ciphertext Non-Replicability

Suppose there is an adversary \(\mathcal{A}\) who can eavesdrop on the channel between the data owner and \(AT\). The purpose of \(\mathcal{A}\) in this game is to obtain the signature of \(AT\) and embed its own \(T^{\prime}\) in the ciphertext and replace the identity of the data owner in the ciphertext data with its own identity, so as to obtain the ownership of the data. We assume that the adversary will not send his identity information to \(AT\) without being able to copy the ciphertext (even if sent, it does not pass authentication). Lemma 2: _Assume that there is a polynomial-time algorithm \(\mathcal{A}\) that can break the **CDH Assumption** with the advantage of \(e\) in the polynomial time, then we can construct a polynomial-time algorithm \(\mathcal{B}\) that falsifies ciphertext with the advantage of \(e\)._

Proof: \(\mathcal{B}\) first runs the \(Setup(1^{\sigma},U)\rightarrow(PK,MSK,PK_{AT},SK_{AT})\) algorithm, and \(PK,PK_{AT}\) are sent to the adversary \(\mathcal{A}\).