# A Fully Secure KP-ABE Scheme on Prime-Order Bilinear Groups through Selective Techniques

Authors: Isaac Amankona Obiri; Qi Xia; Hu Xia; Kwame Opuni-Boachie Obour Agyekum; Kwame Omono Asamoah; Emmanuel Boateng Sifah; Xiaosong Zhang; Jianbin Gao
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Key-policy attribute-based encryption (KP-ABE) is the cryptographic primitive which enables fine grained access control while still providing end-to-end encryption. Although traditional encryption schemes can provide end-to-end encryption, users have to either share the same decryption keys or the data have to be stored in multiple instances which are encrypted with different keys. Both of these options are undesirable. However, KP-ABE can provide less key overhead compared to the traditional encryption schemes. While there are a lot of KP-ABE schemes, none of them simultaneously supports multiuse of attributes, adaptive security, monotone span programs, and static security assumption. Hence, we propose a fully secure KP-ABE scheme for monotone span programs in prime-order group. This scheme uses selective security proof techniques to obtain the requisite ingredients for full security proof. This strengthens the correlation between selective and full security models and enables the transition of the best qualities in selective security models to fully secure systems. The security proof is based on decisional linear assumption and three-party Diffie–Hellman assumption.


---

## Body

## 1. Introduction

Attribute-based encryption (ABE) is a public key cryptosystem which yields fine grained access control over ciphertext. Succinctly put, the ABE system allows ciphertext and key to be linked to a set of attributes such that the decryption of a particular ciphertext is feasible only if the set of attributes of a user’s secret key satisfies the attributes of the ciphertext. In key-policy ABE (KP-ABE) construction for instance, a message is encrypted over attribute set such as “profession: nurse, sex: female, and institution: hospital A,” and keys are generated over access policy like “profession: nurse ∧ sex: female.” The decryption of a given ciphertext is feasible only if the attributes satisfy the access policy. Ciphertext-policy ABE (CP-ABE) construction is a dual version of KP-ABE scheme with the ciphertext and key attached to access policy and attributes, respectively [1–3].ABE is useful cryptographic primitive when data are outsourced in untrusted repositories such as third-party cloud servers. ABE provides an efficient mechanism to share the outsourced data with multiple users based on the user’s roles or attributes. While traditional encryption methods can provide end-to-end encryption, users have to either share the same decryption keys or the data have to be stored in multiple instances which are encrypted with different keys. Both of these options are inappropriate. However, ABE can provide less key overhead compared to traditional encryption methods. ABE offers fine grained access control while still providing end-to-end encryption. In the public repository, a malicious user can obtain the stored encrypted data which do not match his/her attributes’ secret key; however, the user cannot access the content of the data without decipherable keys.Suppose that a patient encrypts his or her personal health data with the attributes{Hospital A, Hospital B, doctor, nurse} and the access control policy is {{{Hospital A}and{nurseordoctor}} or {{Hospital Band{nurseordoctor}}}. With this access policy, any nurse or doctor in one of the hospitals satisfies the access policy requirement and can access the encrypted data. This example is visualized in Figure 1.Figure 1
Example of using ABE in sharing personal health data.However, in this scenario, the challenge is that the attributes “nurse” and “doctor” have been used in the access policy multiple times. An ABE scheme with a single-use of attributes restriction requires that an attribute must appear only once in the access structure. [3]. One caveat way to overcome this single use of restriction is to fix multiple attributes for each use of the attributes such as nurse-1, doctor-1, nurse-2, doctor-2, and so on, in advance. However, there are two problems with this solution. The first is that the maximum number of similar attributes appearing in the access policy should be determined at the setup stage. Hence, the access policy supported by the scheme become restricted. The second one is that, in KP-ABE, for example, this solution blows up the size of ciphertext relative to the maximum number an attribute is reused, which yields reduction in performance. Conversely, in a KP-ABE construction that supports multiple attributes usage, policies are not constrained and any combination of attributes can be rendered arbitrarily to create a policy. So, in this KP-ABE construction, the size of ciphertext becomes policy-independent and compact.The expressiveness of access policy ensures rich structure of keys and ciphertexts of ABE construction [3]. The more expressive an ABE scheme is, the more space is required for the potential access policies and attributes. This raises substantial obstacles, when proving the security of ABE schemes, since the standard notion of security should impose collusion resistance. Thus, a coalition of unqualified users must not have the ability to aggregate their secret keys to decrypt a ciphertext in which not one of them is approved to decrypt. Therefore, the security proof must consider an adversary who is capable of collecting different keys, not only the private key formally assigned to him/her. This necessitates security reductions to strike a balance between two conflicting objectives: the simulator should be sufficiently strong to provide an adversary with the numerous keys he/she requests adaptively; however, the simulator should also lack vital information about the strategies of the adversary which enables him/her to achieve success. Thus, the procedures of the adversary should be hidden from the simulator. The foremost security proof in the standard model for ABE constructions in [4, 5] adopts a strategy, known as “partitioning,” to reconcile these two objectives. The partitioning proof strategy was formerly employed in the settings of identity-based encryption (IBE) [6–10].With the partitioning proof, the simulator configures the system in such a way that every possible private key is in one of the two spaces: keys which the simulator has the ability to create and which she/he cannot [3]. In order to guarantee that the keys that the adversary queries are within the set of keys that the simulator can produce, the previous works [4, 5, 11] resorted to a weaker security model referred to as “selective security.” Unfortunately, under this model, the adversary must announce the access structure to be attacked before giving the public parameters of the system. This does not seem to be suitable security notion in practice for the high security requirement in the real world applications. At the intermediate phase, this concept of selective security is quite useful, but unsuitable as an ultimate goal. In the settings of IBE, the drawback of selective security was eliminated by giving the simulator the ability to “guess” a partition and terminate whenever the adversary exceeds its limit [10]. Nevertheless, if this approach is used in the ABE schemes, it will lead to exponential loss of security because the ABE scheme has a highly expressive access policy, which makes it difficult to identify a partition that is consistent with the partial power ordering of each key. Moreover, CP-ABE’s selective security is still a challenge and the state-of-the-art approach in [5] introduced “q-type” assumption into the fully secure ABE constructions. The q-type assumption in [5] resulted from the need to encode small public parameters with a potentially large access policy. However, since this assumption is extremely complex to understand and also vulnerable to Cheon attack [12], it leads us to seek for KP-ABE construction which is proven fully secure under simple static assumptions such as three-party Diffie–Hellman assumption and decisional linear assumption.Dual system of encryption was introduced by Waters [1] to solve the constraints imposed by the partitioning model. In the proof of the dual system of encryption, the simulator is incessantly configured to produce every key and the challenge ciphertext the adversary requests. The principal idea of the technique is that there are two categories of keys and ciphertexts, namely, “normal” and “semifunctional,” which the simulator can produce [1]. A ciphertext can be decrypted with a key when both the key and the ciphertext are not semifunctional. The combination of ciphertext and a key, both semifunctional, triggers failed decryption because in the semifunctional space, the hidden objects are not cancelled. The semifunctional keys and ciphertext are used in hybrid proof while the normal key and ciphertext are used in the actual system. In the hybrid proof, the adversary is given either normal or semifunctional ciphertext and the secret key that is progressively given to him/her is converted to semifunctional one after the other until it gets to a point where the simulator only issues semifunctional key in the security game. At this point, it becomes easy to prove the security.The critical step in the hybrid proof is when a key becomes semifunctional. At this stage, depending on the proposition that the key (now semifunctional) cannot correctly decrypt the challenge ciphertext, we indicate that the adversary cannot recognize the subtle change in the key. However, since the simulator does not need a partition, she/he cannot be restricted from generating a key and testing the workability of the key by himself/herself via decrypting a semifunctional ciphertext with the key. This challenge in dual encryption proof was resolved in [13] by guaranteeing that the simulator generates only a key decipherable with a semifunctional ciphertext so that the decryption is not hindered from the perspective of the simulator irrespective of whether the semifunctional object exists or not. This type of key formed by the simulator is known as “nominal semifunctional key.” Conversely, in the perspective of the adversary who is restricted from requesting a qualified key, the decryption of the “semifunctional ciphertext” with the “nominal semifunctional key” is hindered. The correlated factor within the nominal semifunctional key and the semifunctional ciphertext which guarantees successful decryption is information-theoretic concealed from the adversary [13]. This presented the first proof of full security in the standard model.Our dual encryption system is constructed over semifunctional and normal space. The semifunctional components of ciphertext and keys are much like the normal component of the actual system except that they are decoupled from the public parameters. This gives us the chance to obtain related parameters in the semifunctional space to create relevant variables during the course of simulation rather than to have all the parameters fixed up in the setup phase. The semifunctional space can supply fresh parameters to the simulator for key isolation mechanism; this implies that every semifunctional key should have unique distribution through the use of fresh parameters in the semifunctional space. When the simulator first issues a secret key, then the challenge access policy is known before the semifunctional parameters are defined. Based on the known access policy, the simulator can embed a difficulty in the secret key from the semifunctional space and later annul this difficulty in the ciphertext. On the other hand, if a ciphertext is first issued, then the attribute set of the challenge ciphertext is known before semifunctional parameters are specified. Based on the known attributes, the simulator can also embed a difficulty in the ciphertext from the semifunctional space and later annul this difficulty in the key. The difficulty is random variables chosen in the semifunctional space with their attachment to either the secret key or the ciphertext rendering invalid decryption unless those variables are cancelled out. The difficulty which is embedded in either the key or the ciphertext requires a complete set of key’s component to cancel it out. However, based on the restriction that the adversary cannot obtain complete components of a secret key, computationally this difficulty is unknown to him/her. Therefore, the two selective ways of embedding difficulties to prevent correct decryption of ciphertext can be combined to attain full security in the standard model.


### 1.1. Our Contribution

We present a KP-ABE scheme in the prime-order settings that supports monotone span program for access policies. The construction achieves full security through selective techniques. Our scheme is based on simple security assumption such as three-party Diffie–Hellman assumption and decisional linear assumption. In summary, our KP-ABE scheme simultaneously achieves the following results:(1)
It enables arbitrary usage of attributes in the access policy.(2)
It achieves adaptive security through selective techniques in the standard model.(3)
It depends on static assumption in the standard model.(4)
It supports span program matrix.(5)
It has compact ciphertext size.


## 1.1. Our Contribution

We present a KP-ABE scheme in the prime-order settings that supports monotone span program for access policies. The construction achieves full security through selective techniques. Our scheme is based on simple security assumption such as three-party Diffie–Hellman assumption and decisional linear assumption. In summary, our KP-ABE scheme simultaneously achieves the following results:(1)
It enables arbitrary usage of attributes in the access policy.(2)
It achieves adaptive security through selective techniques in the standard model.(3)
It depends on static assumption in the standard model.(4)
It supports span program matrix.(5)
It has compact ciphertext size.


## 2. Related Works

ABE, which evolved from IBE, was initially designed by Shamir [14] and then constructed in [6, 15]. Horwitz and Lynn [16] expanded this idea to hierarchical identity-based encryption (HIBE) which was firstly constructed by Gentry and Silverberg [17]. In the standard model, some earlier ABE constructions [8–10, 18] were proven to be selectively secure. Also, ABE construction has been proven to be secure in the generic group model [19]. Dual encryption proofing techniques were also further explored in the study of [20, 21] and applied to attain leakage resilience in [22–24] and applied directly to computational assumptions in [25]. Lewko and Waters [3] developed new methodology to prove full security by integrating selective techniques used to prove selective security for KP-ABE and CP-ABE constructions. However, they used “q-type assumption” in the security proof which is susceptible to attack [12]. From the studies in [12], it can be inferred that as “q” grows larger, the “q-type” assumption becomes stronger and the scheme which requires it becomes vulnerable, particularly if “q” scales in a predictable way. Recently, Tomida et al. [26] and Kowalczyk et al. [27] proposed ABE schemes that address the problem of one-use restriction of attributes in access policy. The schemes were built on a piecewise guessing framework developed in [28], and they proved adaptive security of the ABE constructions with some polynomial security losses. Nonetheless, these schemes do not directly support span programs (linear secret sharing scheme matrix) to express policies. Song et al. [29] proposed attribute-based encryption which enables users to request for their attribute private keys without revealing their attributes to the key generator. Even though this scheme ensures users’ attributes privacy, it is not fully secure and it does not ensure multiuse of attributes. Recently, Khan et al. [30] proposed efficient attribute-based encryption with repeated attribute optimization. The authors employed “RAO” algorithm to remove repeated redundant attribute shares in encryption operations to reduce ciphertext size and computational cost. However, the limitation of this scheme is that the security is proven in selective model. Also, the scheme is not proven secure against chosen ciphertext attacks but rather chosen plaintext attacks under generic bilinear group model. Hence, the scheme does not achieve full security.Table1 shows the comparison of our scheme with other KP-ABE schemes which satisfy full security (adaptive security) notion. Note that adaptive security just refers to an adversary who does not execute all the queries at once (batch queries), but rather adapts her/his queries from previous results (see Definition 10). The last row describes our scheme in Section 4. From Table 1, it can be seen that JL [26] scheme possesses most of the needed properties of ABE construction. However, this scheme inherits the problem of polynomial security losses from the “piecewise guessing framework” that was used for its construction. Also, the security of schemes JL [26] and LK [27] was proven in random oracle model. Therefore, from the authors’ point of view, there is no scheme that simultaneously achieves the properties listed in Section 1.1. and that is still able to retain the efficiency of selective security in the standard model.Table 1
Comparison of KP-ABE schemes which have adaptive security.
SchemeMspAssumptionCompactMultiuseFull (adaptive) securityGSW [31]✓Static ✓✓Lw [3]✓q-type✓✓✓CGK [32]✓k-Lin ✓✓JL [26]Static ✓✓✓✓LK [27]Static ✓✓✓Ours✓Static ✓✓✓✓


### 2.1. Organization

In Section3, we revise the important concepts on KP-ABE systems in prime-order bilinear groups, along with formal definitions of the complexity assumptions. In Section 4, we provide the construction of our scheme and demonstrate its correctness. Section 5 shows security proof of the scheme. In Section 6, we provide implementation and evaluation of the proposed scheme and other related schemes. Finally, in Section 7, we conclude the work.


## 2.1. Organization

In Section3, we revise the important concepts on KP-ABE systems in prime-order bilinear groups, along with formal definitions of the complexity assumptions. In Section 4, we provide the construction of our scheme and demonstrate its correctness. Section 5 shows security proof of the scheme. In Section 6, we provide implementation and evaluation of the proposed scheme and other related schemes. Finally, in Section 7, we conclude the work.


## 3. Preliminaries

Definition 1.
(access structure) [33]. Let P=ρ1,ρ2,…,ρn be a set of parties. A collection A⊆2P is monotone if B∈A and B⊆C imply that C∈A. An access structure (respectively, monotone access structure) is a collection of nonempty subsets of P. The sets in A are authorized sets, and the sets not in A are nonauthorized sets.Definition 2.
(linear secret sharing scheme). A linear secret sharing scheme is made of two algorithms, share and reconstruct. To distribute a secrets∈ℤp among n parties, the share algorithm sets r1=s, randomly selects r1,r2,…,rt∈ℤpt, and computes ρi=∑k=1trkik for all 1≤i≥n. The shadows or shares ρi=λi are distributed to n distinct parties. Since the secret is the constant term s=r1=ρ1, the reconstruct algorithm recovers the secret from any t shares λi, for the attribute set S⊨A and I=i|ρi∈S, by computing the linear function of the shares as ∑i∈Iωiλi=s, where each constant ωi=∏j∈I,j≠ii/j−1 can be obtained efficiently in the polynomial time.Definition 3.
(monotone span program (msp)) [34]. A msp is a linear algebraic model for computing monotone functions. Let ℤ be a field and w1,…,wn be variables. A msp is a tuple Δ=M,ρ where M∈ℤt×n is a matrix and ρ:1,2,…,ρt=w1,…,wn is labelling function. The msp Δ actualizes the monotone access structure A⊂2P where B∈A if and only if n is spanned by the rows of the matrix M whose labels belong to B. The size of Δ is t, and the number of rows in M. With regard to secret sharing, the size of the msp is the total number of shares that are given to all parties in P.Definition 4.
(bilinear groups). A group generating algorithmG takes a secret parameter λ and returns a description of a group G⟶p,G,GT,g,e, where p is a prime number, G and GT are cyclic groups of order p, g∈G is a generator, and e:G2⟶GT is a bilinear map, which has two properties:(1)
Bilinearity:∀g,h∈G,z,y∈ℤp,egz,hy=eg,hzy.(2)
Nondegeneracy: for generatorsg and h, eg,h≠1.Definition 5.
(the decisional linear (DLIN) assumption). With a given group generating algorithmG, we define the following distribution:(1)G≔G,p,GT,e←$G,g,b,d←$G,a1,a2←$ℤp,D←G,g,b,d,ba1,da2,T0←ga1+a2,T1←G.
The advantage an algorithmA has in breaking this assumption is(2)AdvG,AdLλ≔|PAD,T0=1−PAD,T1=1.
We declare that DLIN assumption is satisfied byG, if for any probabilistic polynomial time (PPT) algorithm A, AdvG,AdLλ is negligible.Definition 6.
(the three-party Diffie–Hellman (TPDH) assumption). With a given group generating algorithmG, we define the following distribution:(3)G≔G,p,GT,e←$G,g←$G,x,y,z←$ℤp,D←G,gx,gy,gz,T0←gxyz,T1←G.
The advantage an algorithmA has in breaking this assumption is(4)AdvG,A3PDHλ≔|PAD,T0=1−PAD,T1=1.
We declare that TPDH assumption is satisfied byG, if for any probabilistic polynomial time (PPT) algorithm A, AdvG,A3PDHλ is negligible.Definition 7.
(dual pairing vector spaces). We follow the definition of double vector pairing spaces in [35, 36]. For u⇀ = u1,…,un∈ℤpn and g∈G, we write gu⇀ to represent the n-tuple of elements of G:(5)gu⇀≔gu⇀1,…,gu⇀n.
We can execute scalar product and exponentiation in the exponent. For anya∈ℤp and u⇀,v⇀∈ℤpn, we have(6)gau⇀≔gau⇀1,…,gau⇀n,gu⇀+v⇀≔gu⇀1+v⇀1,…,gu⇀n+v⇀n.
We define a bilinear mapen to represent the product of the componentwise pairings:(7)engu⇀,gv⇀≔∏i=1ngu⇀i,gvi⇀=eg,gu⇀.v⇀.
Here, the dot product is executed using modulop. We select two random sets of vectors: B≔b⇀1,b⇀2,…,b⇀n and B∗=b⇀1∗,b⇀2∗,…,b⇀2∗ of ℤpn subject to the following constraints:(1)
The basisB with the family b⇀i and dual basis B∗ with the family b⇀i∗ are dual orthonormal when b⇀i⋅b⇀j∗=0modp, for i,j=1,…,n}, whenever i≠j. Therefore, the two vectors are perpendicular to each other. As a consequence, their dot product yields zero.(2)
Conversely,b⇀i is orthonormal to b⇀i∗ when they have the same index, i.e., b⇀i⋅b⇀j∗=δmodp, for i,j=1,…,n whenever i=j, where δ denotes nonzero element of ℤp. Here, it can be seen that we have abused the terminology “orthonormal,” since δ is not constrained to 1.
Note that the random selection ofB,B∗ from the sets that satisfy requirements of dual orthonormality can be done by selecting a set of n vectors (i.e., b⇀1,b⇀2,…,b⇀n∈B) at uniformly random from ℤpn . Then, each vector B∗ is determined from the orthonormality constraint such that under high probability, the vectors B,B∗ are linearly independent.Definition 8.
(the subspace assumption). With a given group generating algorithmG, we define the subspace assumption as(8)G≔G,p,GT,e←$G,g←$G,δ,η,β,τ1,τ2,τ3,μ1,μ2,μ3←$ℤp,B1,B1∗←$Dualℤpn1,δ,…,Bm,Bm∗←$Dualℤpnm,δ,d,U1,i≔gμ1γ1b⇀1,i+μ2γ2b⇀ki+1,i+μ3γ3b⇀2ki+1,i,U2,i≔gμ1γ1b⇀2,i+μ2γ2b⇀ki+2,i+μ3γ3b⇀2ki+2,i,…,Uki,i≔gμ1γ1b⇀kii,+μ2γ2b⇀ki,i+2,i+μ3γ3b⇀2ki,i+2,i,∀i∈m,V1,i≔gτ1ηb⇀1,i∗+τ2βb⇀ki∗+1,i,V2,i≔gτ1ηb⇀2,i∗+τ2βb⇀ki∗+2,i,…,Vki,i≔gτ1ηb⇀ki,i∗+τ2βb⇀2ki,i∗,∀i∈m,W1,i≔gτ1ηb⇀1,i∗+τ2βb⇀ki∗+1,i+τ3b⇀ki∗+1,i,W2,i≔gτ1ηb⇀2,i∗+τ2βb⇀ki∗+2,i+τ3b⇀2ki∗+2,i,…,Wki,i≔gτ1ηb⇀ki,i∗+τ2βb⇀2ki,i∗+τ3b⇀3ki,i∗,∀i∈m,D≔G,g,gb⇀1,i,gb⇀2,i,…,gb⇀2ki,i,gb⇀3ki+1,i,…,gb⇀ni,i,gηb⇀1,i∗,…,gηb⇀ki,i∗,gβb⇀ki+1,i∗,…,gβb⇀2ki∗,i,gb⇀2ki+1∗,i,…,gb⇀ni,i∗,U1,i,U2,i,…,Uki,ii=1m,μ3.
We assert that for any PPT algorithmA which returns a value in 0,1,(9)AdvG,A≔PAD,V1,i,…,Vki,ii=1m=1−PAD,W1,i,…,Wki,ii=1m=1is negligible in the security parameter λ. The subspace assumption is the application of the DLIN assumption with vectors. The proof of this assumption can be found in pages 37-38 [3].Definition 9.
(KP-ABE scheme). Under standard definition, a key-policy attribute-based encryption scheme has a quintuple algorithmsetup,Enc,KeyGen,Dec:(1)
SetupU,1λ⟶msk,pp: it takes attribute universe description U and a security parameter 1λ. It returns a master secret key msk and public parameters pp.(2)
Encmsg,pp,S⟶ct: it takes message msg, public parameters pp, and the set of attributes S. It outputs the ciphertext ct.(3)
KeyGenpp,msk,A⟶skA: it takes public parameters pp, master secret key msk, and an access structure A. It outputs a secret key skA.(4)
Decpp,ct,skA⟶msg: it takes public parameters pp, ciphertext ct, and secret key sk and returns a message msg or ⊥.


### 3.1. Correctness

KP-ABE construction is correct if it meets the following requirements. With a given ciphertext and a secret key, if the ciphertext attribute’s set matches the key’s access structure, then for anymsg∈Msg, we have(10)msg=msg∗|pp,msk←Setup1λ,Uct←Encpp,msg,SskA←KeyGenpp,msk,Amsg∗←Decpp,ct,skA.Definition 10.
(KP-ABE full security model). The security game between the challengerC and adversary A proceeds as follows.
The security definition for fully secure KP-ABE depends on indistinguishable game with PPT-chosen plaintext attacker. The game proceeds as follows:(1)
Setup: the challengerC executes Setup1λ,U⟶pp,msk and submits pp to adversary A.(2)
Phase 1:A adaptively queries C for the secret keys corresponding to a set of access structures A1,…,AQ1. For each time, it obtains skA←KeyGenpp,msk,Ak from C.(3)
Challenge:A sends two messages msg0∗,msg1∗ of equal size together with the set of attributes S∗ to C. Then, C tosses a binary coin b and executes ct∗←Encpp,msgb∗,S∗ and gives ct∗ to A on a condition that S∗ does not satisfy any of the access structures queried in phase 1.(4)
Phase 2:A adaptively queries C for the secret keys corresponding to the set of access structures AQ1+1,…,AQ with the condition that none of these satisfy S∗. For each time, it obtains skA←KeyGenpp,msk,Ak from C.(5)
At the end,A returns b∗ as a guess for b, and the adversary A is a winner if b=b∗. The advantage of A for this indistinguishable game is defined as(11)AdvAGamereal=Pb=b∗−12.Definition 11.
A KP-ABE construction is fully secure if PPT algorithmA has negligible advantage in the above security game.
Note that with the selective security game, the adversary must announceA before viewing the pp. Henceforth, the term semifunctional will be denoted as SF.


## 3.1. Correctness

KP-ABE construction is correct if it meets the following requirements. With a given ciphertext and a secret key, if the ciphertext attribute’s set matches the key’s access structure, then for anymsg∈Msg, we have(10)msg=msg∗|pp,msk←Setup1λ,Uct←Encpp,msg,SskA←KeyGenpp,msk,Amsg∗←Decpp,ct,skA.Definition 10.
(KP-ABE full security model). The security game between the challengerC and adversary A proceeds as follows.
The security definition for fully secure KP-ABE depends on indistinguishable game with PPT-chosen plaintext attacker. The game proceeds as follows:(1)
Setup: the challengerC executes Setup1λ,U⟶pp,msk and submits pp to adversary A.(2)
Phase 1:A adaptively queries C for the secret keys corresponding to a set of access structures A1,…,AQ1. For each time, it obtains skA←KeyGenpp,msk,Ak from C.(3)
Challenge:A sends two messages msg0∗,msg1∗ of equal size together with the set of attributes S∗ to C. Then, C tosses a binary coin b and executes ct∗←Encpp,msgb∗,S∗ and gives ct∗ to A on a condition that S∗ does not satisfy any of the access structures queried in phase 1.(4)
Phase 2:A adaptively queries C for the secret keys corresponding to the set of access structures AQ1+1,…,AQ with the condition that none of these satisfy S∗. For each time, it obtains skA←KeyGenpp,msk,Ak from C.(5)
At the end,A returns b∗ as a guess for b, and the adversary A is a winner if b=b∗. The advantage of A for this indistinguishable game is defined as(11)AdvAGamereal=Pb=b∗−12.Definition 11.
A KP-ABE construction is fully secure if PPT algorithmA has negligible advantage in the above security game.
Note that with the selective security game, the adversary must announceA before viewing the pp. Henceforth, the term semifunctional will be denoted as SF.


## 4. Prime-Order KP-ABE Construction

We use the dual framework of data encryption proof technique in prime-order settings, where orthogonal subspaces within the exponents perform the role of both normal and SF components. Since SF vectors are never published, they can serve as “hidden parameters” which create new randomness even with a fixed size of public parameters. We provide fresh pair of vectors for each attribute to produce enough randomness to ensure an information-theoretic transition from a nominal SF key (one with SF components but still capable of correctly decrypting SF ciphertext) to a real SF one (a key which is incapable of decrypting SF ciphertext). Again, we denote the attribute universeU=1,2,…,U as the complete number of attributes within the system. The scheme is constructed as follows:(1)
Setup1λ,U⟶pp,msk: this algorithm picks a bilinear group G of prime order p and a generator g. It picks at random two pairs of dual orthonormal bases B,B∗,B0,B0∗ of dimension 3 and U pairs of dual orthonormal bases B1,B1∗,…,BU,BU∗ of dimension 6, bound to the restriction that they all hold the same value δ. We let b⇀i,b⇀i∗ denote the family vectors of B,B∗, and b⇀i,j,b⇀i,j∗ are the basis vectors of Bj,Bj∗ for each j from 0 to U. The setup algorithm also picks a quadruple of random exponents α1,α2,r1,r2←$ℤp and another quadruple of random exponents y1,y2←$ℤp, y1∗,y2∗←$ℤ with the restriction that ∀i=j,yi⋅yi∗=1. The public parameters comprise(12)pp=G,p,gy1b⇀1,i,gr1b⇀1,i,gy2b⇀2,i,gr2b⇀2,i,gr1b⇀3,gr2b⇀4,eg,gα1δ,eg,gα2δ,∀i∈U.Additionally, the master secret keymsk is(13)msk=α1,α2,gy1∗b⇀1,i∗,gr1b⇀1,i∗,gy2∗b⇀2,i∗,gr2b⇀2,i∗,gr1b⇀3∗,gr2b⇀4∗,∀i∈U.(2)
KeyGenpp,msk,A=M,ρ⟶skA: the algorithm gets the public key pp, a master key msk, and access structure A=M,ρ, and the algorithm picks randomly z1,z2,…,zt,r1,r2,…,rt∈ℤpt. Then, set z1=α1,r1=α2 and compute the shares λi=∑k=1tzkik and ωi=∑k=1trkik for all 1≤i≥n, where i1,i2,…,it is the vector of Mi∈M which corresponds to the i-th row of M. It then picks randomly a1,a2∈ℤp and outputs(14)skA=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗K2=ga1r1b⇀3∗+a2r2b⇀4∗,i∈ρi.(3)
Encmsg,S,pp⟶ct: the algorithm gets the message msg, attribute sets S, and public parameter pp, picks randomly s1,s2←ℤp, and outputs(15)ct=C0=msg⋅eg,gα1s1δ+α2s2δ,C1,i=gs1y1b⇀1,i+s2y2b⇀2,iC2=gs1b⇀3+s2b⇀4,∀i∈S.(4)
Decct,skA⟶msg: let S∗ correspond to the set of attributes associated to ciphertext ct and M be the policy matrix. If S∗ satisfies A, the decryption algorithm computes α1=∑i∈S∗λiσi and α2=∑i∈S∗ωiσi, where each constant σi=∏j∈S∗,i≠ji/j−1 can be obtained efficiently in the polynomial time. It then computes(16)Ω=∏i∈S∗e6K1,i,C1,ie3K2,C2=∏i∈S∗e6gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗,gs1y1b⇀1,i+s2y2b⇀2,ie3ga1r1b⇀3∗+a2r2b⇀4∗,gs1b⇀3+s2b⇀4σi=∏i∈S∗e6gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗,gs1y1b⇀1,i+s2y2b⇀2,ie6gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗,gs1y1b⇀1,i+s2y2b⇀2,ie3ga1r1b⇀3∗+a2r2b⇀4∗,gs1b⇀3+s2b⇀4σi=∏i∈S∗e6g,gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗s1y1b⇀1,i+s2y2b⇀2,ie6g,gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗s1y1b⇀1,i+s2y2b⇀2,ie3g,ga1r1b⇀3∗+a2r2b⇀4∗s1b⇀3+s2b⇀4σi=∏i∈S∗e6g,gλis1y1y1∗b⇀1,i∗b⇀1,i+a1r1s1y1y1∗b⇀1,i∗b⇀1,ie6g,gωis2y2y2∗b⇀2,i∗b⇀2,i+a2s2y2r2y2∗b⇀2,i∗b⇀2,ie3g,ga1r1s1b⇀3b⇀3∗+a2r2s2b⇀4∗b⇀4σi=∏i∈S∗eg,gλis1δ+a1r1s1δeg,gωis2δ+a2r2s2δeg,ga1r1s1δ+a2r2s2σi=eg,g∑i∈S∗λi⋅σis1δeg,g∑i∈S∗ωi⋅σis2δ,Ω=eg,gα1s1δeg,gα2s2δ.Then, the message is retrieved as(17)msg=C0Ω,msg=msg⋅eg,gα1s1δeg,gα2s2δeg,gα1s1δeg,gα2s2δ.


## 5. Security Proof

Theorem 1.
Under the DLIN assumption and TPDH assumption defined in Section3, our KP-ABE construction is fully secure (i.e., see Definition 11).The security proof for our construction depends on hybrid argument over series of games. We will define the set of keys and ciphertext that will be used in the games. To commence the security game, first the challenger generatesgb⇀5,i,gb⇀5,i∗←Bi,Bi∗←$Dualℤp6,δ and gb⇀6,gb⇀6∗←B,B←$Dualℤp3,δ as the related parameters that will be used in the security proof.


### 5.1. SF Ciphertext

To create this ciphertext for a set of attributesS, firstly, we execute the normal encryption algorithm in equation (15). The ciphertext is made up of the following components: C0,C1,i,∀i∈S,C2. Then, we pick random valuesB,B∗←$Dualℤp3,δS3∈ℤp and multiply C1,i by gs3b⇀5,i. Also, we multiply C2 by gs3b⇀6. The other component of the ciphertext stays unaltered as shown below.(18)ct=C0=msg⋅eg,gα1s1δ+α2s2δ,C1,i=gs1y1b⇀1,i+s2y2b⇀2,igs3b⇀5,iC2=gs1b⇀3+s2b⇀4gs3b⇀6,∀i∈S.


### 5.2. SF Keys

To generate these keys for anmspM,ρ, we first execute the normal key generation algorithm in equation (14) to get a normal key made up of the following components of K1,i∈ρi,K2. We then pick random secret values a3,α3∈ℤp and a random vector v=r1,…,rt∈ℤpt and set the index r1=α3. We produce shares for the secret as Φi=Mi⋅vT, where Mi is the row vector in M with the label ρi. The SF key is output as(19)skA=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗⋅gΦib⇀5∗,i+a3b⇀5∗,iK2=ga1r1b⇀3∗+a2r2b⇀4∗⋅ga3b⇀6∗,i∈ρi.Recall that we do not put a partition on a simulator with a nominal SF key. Therefore, the nominal SF key correlates correctly with the SF ciphertext to allow decryption, regardless of the presence or absence of SF components. This happens because the share of the secretα3 in the SF space is zero.


### 5.3. Ephemeral SF Keys

These keys are indistinguishable to nominal keys, with the exception that SF components attach to eitherK1,i or K2 which is now being randomized (which prevent accurate SF ciphertext decryption). Concretely, to create an ephemeral SF key for the access matrix M, we first execute the normal key generation algorithm in equation (15) to get a normal key made up of the following components of K1,i∈ρi, K2. We then pick random secret values a3,a4, a5,α3∈ℤp and a random vector v=r1,…,rt∈ℤpt and set the index r1=α3. Note that value of the secret α3 in the SF space is zero. We produce shares for the secret as Φi=Mi⋅vT, where Mi is the row vector in M with the label ρi. The SF key is output as(20)skA=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗⋅ga4Φib⇀5∗,i+a3b⇀5,i∗K2=ga1r1b⇀3∗+a2r2b⇀4∗⋅ga3b⇀6∗,i∈ρi.


### 5.4. Proof Structure

The hybrid proof is executed over a series of games. DenotingQ as the total number of key requested by adversary, we define the series of games as follows: Gamereal is the real security game as in Section 3 (see Definition 10). In Gamek, the ciphertext submitted to the adversary is SF, as are the first k keys. The rest of the keys are normal. GamekN is similar to Gamek, besides the fact that the k-th key delivered to the adversary is nominal SF key. The first k−1 keys are SF, whereas the rest of the keys are normal. GamekT is similar to Gamek, besides the fact that the k-th key delivered to the adversary is an ephemeral SF. The first k−1 keys are SF, whereas the rest of the keys are normal. Gamefinal is analogous to GameQ, besides the fact that the SF ciphertext delivered to the adversary is encryption of random message.The layout of our hybrid argument will be as follows. Firstly, we move fromGamereal to Game0, then to Game1, next to Game2, and so on. Eventually, we get to GameQ, where all of the keys and the ciphertext delivered to the adversary are SF. Then, we move to Gamefinal and this completes our security proof since any adversary in the final game has negligible advantage. The transition from Gamereal to Game0 and from GameQ to Gamefinal is not complicated and can be done with the help of the computational assumptions. However, the transition from GameK−1 to Gamek is a bit complicated and requires other steps. For these steps, we will consider making transition between two phases. Phase 1 is when the adversary requests a challenge ciphertext after obtaining the secret key. In phase 2, the adversary requests a secret key after obtaining the challenge ciphertext. Therefore, in order to get from Gamek−1 to Gamek, we will transition first from Gamek−1 to GamekN, then to GamekT, and finally to Gamek. We let Q1 represent the number of queries in phase 1, and we will tackle this transition independently for k≤Q1 and k≥Q1. The security proof for phase 1 queries and phase 2 queries is similar to the selective security proof in the KP-ABE settings and CP-ABE settings, respectively.Lemma 1.
Under the subspace assumption, no PPT adversary can achieve a non-negligible advantage in distinguishingGamereal and Game0.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing Gamereal from Game0, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption as B,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating Gamereal and Game0 is described as follows :(1)
G,p,gd⇀3,gd⇀4,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ←C;(2)
b←$0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←$ℤp;(3.2)
letΓ0:=T1,i⟵gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2⟵gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1:=T1,i⟵gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2⟵gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀iU;(3.3)
returnC←b?Γb;(3.4)(4)
α1,α2←$ℤp;(5)
α1←ηα1,α2←βα2;(6)
let pp=G,p,gd⇀1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,e6gd⇀1,i,gηd⇀1,i∗α1,e6gd⇀2,i,gβd⇀2,i∗α2;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀2←$ℤpt;(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(8.7)
letK2=T2;(8.8)
fori=1toQ1;(8.8.1)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8.2)
letd⇀2,i∗⟶d⇀2,i∗ωi;(8.8.3)
letd⇀5,i∗⟶d⇀5,i∗Φi;(8.8.4)
writeK1,i=gy1∗ηd⇀1,i∗T1,i;(8.8.5)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,y1,y2←$ℤp(13)
letC0=msgb.eg,gα˜1s˜1δ+α˜2s˜2δ;(14)
letC2=gs1b⇀3+s4b⇀4=gd⇀3s˜1⋅gd⇀4s˜2;(15)
foritoS∗(15.1)
guideS∗⊭A1;(15.2)
Writegs1y1b⇀1,i+s2y2b⇀2,i=gd⇀1,is˜1+γ1gd⇀2,is˜2+γ2;(15.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(16)(17)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(17.1)
y1∗,α3,←$ℤp;(17.2)
Cpp,α1,α2,α3,Γ0,Γ1(17.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(17.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(17.5)
letωi←M1T∗v⇀2, where α2 is the secret;(17.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(17.7)
letK2=T2;(17.8)
fori=Q1+1toQ(17.8.1)
guard (A1⊭S∗)(17.8.2)
letd⇀1,i∗⟶d⇀1,i∗λi;(17.8.3)
letd⇀2,i∗⟶d⇀2,i∗ωi;(17.8.4)
letd⇀5,i∗⟶d⇀5,i∗Φi;(17.8.5)
writeK1,i=gy1∗d⇀1,iT1,i(17.8.6)
OutputK1,i,K2∀i∈A1⟶A(18)
b=b′
To simulate eitherGamereal or Game0, Algorithm C sets the bases for the construction as(21)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈U,b⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseD∗,D,D0∗,D0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ηα1,α2=βα2. Then, C produces(22)eg,gα1s1=e6gd⇀1,i,gηd⇀1,i∗α1,eg,gα2s2δ=e6gd⇀2,i,gβηd⇀2,i∗α2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure which is enforced by the guard. In line 17, A requests for the private key K1,i,K2∀i∈A1 for the second time. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, CoutputsA’s guess as its own guess. By analysing this game, when the τ3 terms are absent in the private key, then C correctly simulates GameReal. In this instance, Γ0 is used in generating the private key. When τ3 terms are present, then C correctly simulates Game0. In this case, Γ1 is used in generating the private key. Therefore, C can capitalize on algorithm A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against subspace assumption.Lemma 2.
Under the subspace assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamek−1 and GamekN for any k from 1 to Q.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GameK−1 from GamekN, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption as B,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating Gamek−1 and GamekN is described as follows:(1)
G,p,gd⇀3,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ,U←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←$ℤp;(3.2)
letΓ0≔T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1≔T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀i∈U;(3.3)
returnC←b?Γb;(3.4)(4)
EncGen(4.1)
letμ1,μ2,μ3,y1,y2←$ℤp;(4.2)
letΓ0∗=U1,i←gμ1γ1b⇀1,i+μ2γ2b⇀2,i,U2←gμ1γ1b⇀3+μ2γ2b⇀4Γ1∗=U1,i←gμ1γ1b⇀1,i+μ2γ2b⇀2,i+μ3b⇀5,i,U2←gμ1γ1b⇀3+μ2γ2b⇀4+μ3b⇀6∀i∈U;(4.3)
returnC←b?Γb∗;(4.4)(5)
α1,α2←$ℤp;(6)
let pp=G,p,gd1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,engd⇀1,gηd⇀1∗α1,engd⇀1,gβd⇀2∗α2;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(8.7)
letK2=T2;(8.8)
fori=1toQ1(8.8.1)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8.2)
letd⇀2,i∗⟶d⇀1,i∗ωi;(8.8.3)
letd⇀2,i∗⟶d⇀1,i∗ωi;(8.8.4)
writeK1,i=gλiy1∗b⇀1,i∗T1,i;(8.8.5)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,s˜3←$ℤp;(13)
lets˜1←μ1,s˜2←μ2,s˜3←μ3;(14)
letC0=msgb⋅eg,gα1s1δ+α2s2δ;(15)
letC2=U2;(16)
foritoS∗(16.1)
guideS∗⊭A1;(16.2)
writeC1,i=U1,i;(16.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(17)(18)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(18.1)
y1∗,α3,←$ℤp;(18.2)
Cpp,α1,α2,α3,Γ0,Γ1(18.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(18.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(18.5)
letωi←M1T∗v⇀2, where α2 is the secret;(18.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(18.7)
letK2=T2;(18.8)
fori=Q1+1toQ(18.8.1)
guard (A1⊭S∗)(18.8.2)
letd⇀1,i∗⟶d⇀1,i∗λi;(18.8.3)
letd⇀2,i∗⟶d⇀2,i∗ωi;(18.8.4)
letd⇀5,i∗⟶d⇀5,i∗Φi;(18.8.5)
writeK1,i=gy1∗d⇀1,iT1,i;(18.8.6)
OutputK1,i,K2∀i∈A1⟶A;(19)
b=b′;
To simulate eitherGameK−1 or GameKN, algorithm C sets the bases for the construction as(23)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈U,b⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseD∗,D,D0∗,D0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ηα1,α2=βα2. Then, C produces(24)eg,gα1s1=engd⇀1,gηd⇀1∗α1,eg,gα2s2δ=engd⇀1,gβηd⇀2∗α2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ,U. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure A1 which is enforced by the guard. In line 18, A requests for the private key K1,i,K2∀i∈A1 for the second time. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, C outputs A’s guess as its own guess. By analysing this game, when the extra components µ3b⇀5,i and µ3b⇀6 on C1,i and C2, respectively, are present, then the ciphertext is SF ciphertext (i.e., Γ∗=Γ1∗); otherwise, it is normal ciphertext (i.e., Γ∗=Γ0∗). Hence, C is capable to simulate normal and SF ciphertext. When the τ3 terms are absent in the private key, then C correctly simulates Gamek−1. In this instance, Γ0 is used in generating the private key. When τ3 terms are present, then C correctly simulates GamekN. In this case, Γ1 is used in generating the private key. Therefore, C can capitalize on algorithm A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against subspace assumption.Lemma 3.
Under the TPDH assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamekN and GamekT for any k from 1 to Q1 (note that these are phase 1 queries).Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GamekN from GamekT, then we will construct a PPT algorithm C to break the TPDH assumption. C gets g,gx,gy,gz where T is either gxyz or random element of G. Algorithm C simulates either GamekN from GamekT based on the nature of T. C picks a random dual orthonormal bases B,B∗,B0,B0∗ of 3 dimensions and B1,B1∗,…,BU,BU∗ of 6 dimensions n, all with the same value δ. The procedure for simulating GamekN and GamekT is described as follows:(1)
G,p,gb⇀3,gb⇀3∗,gb⇀4∗,gb⇀1,i,gb⇀2,i,gb⇀1,i∗,gb⇀2,i∗∀iU,Γ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letx,y,z←ℤp;(3.2)
letb⇀5,i∗←Dualℤp6,δ,b⇀6∗←Dualℤp3,δ;(3.3)
C←g,gx,gy,gz,T;(3.4)
letg,gx,gy,T;(3.5)
returnb⇀5,i∗∀iU,b⇀6∗;b?T←gxyz:T←G1;(3.6)(4)
α1,α2←$ℤp;(5)
let pp=G,p,gb1,i,gb⇀2,i,gb⇀3,gb⇀4∀i∈U,eg,gα1,eg,gα2;(6)
Outputpp⟶A;(7)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(7.1)
Cpp,α1,α2,α3,Γ0,Γ1(7.2)
y1∗,y2∗,α3,r1,r2,a1,a2,a3,a4←$ℤp;(7.3)
leta4=z−1,α3←0∈ℤp;(7.4)
letv⇀1,v⇀2,v⇀3←ℤpt;(7.5)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(7.6)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(7.7)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(7.8)
letK2=ga1r1b⇀3∗+a2r2b⇀4∗+a3cb⇀6∗;(7.9)
fori=Q1+1toQ(7.9.1)
writeK1,i=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗+ωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗TΦia4b⇀5,i∗+a3b⇀5,i∗;(7.9.2)
OutputK1,i,K2∀i∈A1⟶A;(8)(9)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(10)
Cpp,msg0∗,msg1∗,S∗(11)
lets˜1,s˜2,s˜3←$ℤp;(12)
letC0=msgb⋅eg,gα1s˜1δ+α2s˜2δ;(13)
letC2=gs˜1b⇀3+s˜2b⇀4+s˜3b⇀6;(14)
foritoS∗(14.1)
guideS∗⊭A1;(14.2)
letd⇀5,i←Dualℤp6,δ;(14.3)
writeC1,i=gs˜1y1b⇀1,i+s˜2y2b⇀2,i+s˜3b⇀5,i;(14.4)
OutputC0,C1,i,C2∀i∈S∗⟶A;(15)(16)
b=b′;
To simulate eitherGameKN or GameKT, algorithm C sets the bases for the construction as(25)b⇀1,i=d⇀1,i,b⇀2,i=d⇀2,i,b⇀3=d⇀3,b⇀4=d⇀4,b⇀5,i=d⇀5,i,b⇀6=d⇀6∀i∈U,b⇀1,i∗=d⇀1,i∗,b⇀2,i∗=d⇀2,i∗,b⇀3∗=d⇀3∗,b⇀4∗=d⇀4∗,b⇀5,i∗=xy−1d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. The SF components b⇀5,i,b⇀6 and b⇀5,i∗,b⇀6∗ can supply fresh parameters to randomize the ciphertext and the private key, respectively.
In line 1, the TPDH assumption adversaryC is given the public parameters of the system and its challenge T. In line 7, A requests for its private keys, which C replies correctly to. In line 9, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure A1 which is enforced by the guard. Eventually, C outputs A’s guess as its own guess. By analysing this game, if T=gxyz, then the power vector becomes xyzxyz−1Φid⇀5,i∗=Φib⇀5,i∗ as needed for the nominal SF key. Alternatively, this power vector is distributed as random multiples of b⇀5,i∗, which is required for an ephemeral SF key. Hence, when T=gxyz, then C has successfully simulated GamekN, and if T is a random group element, then C has successfully simulated GamekT. Therefore, C can capitalize on A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against the TPDH assumption.Lemma 4.
Under the TPDH assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamekN and GamekT for any k>Q1 (note that these are phase 2 queries).Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing Gamek1 and GamekN for some k such that Q1<k≤Q. We will construct a PPT algorithm C to break the TPDH assumption. C gets g,gx,gy,gz,T where T is either gxyz or a random element of B∗. C will simulate either GamekN or GamekT with algorithm A based on T. C picks a random dual orthonormal bases B,B∗,B0,B0∗ of 3 dimensions and B1,B1∗,…,BU,BU∗ of 6 dimensions, all with the same value δ. The procedure for simulating GamekN and GamekT is described as follows:(1)
G,p,gb⇀3,gb⇀3∗,gb⇀4∗,gb⇀1,i,gb⇀2,i,gb⇀1,i∗,gb⇀2,i∗∀iUΓ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letx,y,z,ri∀i∈s←$ℤp(3.2)
letb⇀5,i∗←$Dualℤp6,δ,b⇀6∗←$Dualℤp3,δ;(3.3)
b⇀5,i∗⟶x−1rid⇀5,i∗∀i∈S;(3.4)
C←g,gx,gy,gz,T;(3.5)
letg,gx,gy,T;(3.6)
returnri,b⇀5,i∗∀iU,b⇀6∗;b?T←gxyz:T←G1;(3.7)(4)
α1,α2←ℤp;(5)
let pp=G,p,gb1,i,gb⇀2,i,gb⇀3,gb⇀4∀i∈U,eg,gα1,eg,gα2;(6)
Outputpp⟶A(7)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(8)
Cpp,msg0∗,msg1∗,S∗(9)
lets˜1,s˜2,s˜3←$ℤp;(10)
letC0=msgb⋅eg,gα1s˜1δ+α2s˜2δ;(11)
letb⇀6←Dualℤp3,δ;(12)
letC2=gs˜1b⇀3+s˜2b⇀4+s˜3b⇀6;(13)
foritoS∗(13.1)
letb⇀5,i←Dualℤp6,δ;(13.2)
writeC1,i=gs˜1y1b⇀1,i+s˜2y2b⇀2,i+s˜3b⇀5,i;(13.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(14)(15)
K1,Q1+1,…,Q1,…,Q1,K2←AA1Q1+1,…,Q with;(15.1)
Cpp,α1,α2,ri,b⇀5,i∗,b⇀6∗,T(15.2)
y1∗,y2∗,α3,r1,r2,a4←$ℤp′(15.3)
letα3←0∈ℤp;(15.4)
Let∑i=1nri⟶ψ,θi←1/ri⋅1/ψ∀i∈S∗;(15.5)
leta4←y−1,z=ψ;(15.6)
letv⇀1,v⇀2,v⇀3←$ℤpt(15.7)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(15.8)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(15.9)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(15.10)
guideS∗⊭A1;(15.11)
letK2=ga1r1b⇀3∗+a2r2b⇀4∗+a3cb⇀6∗;(15.12)
fori=Q1+1toQ(15.12.1)
letΦi˜←Φiθi;(15.12.2)
writeK1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗+ωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗Ta4Φi˜b⇀5,i∗+a3b⇀5,i∗;(15.12.3)
OutputK1,i,K2∀i∈A1⟶A;(16)
b=b′;
To simulate eitherGamekN or GamekT, algorithm C sets the bases for the construction as(26)b⇀1,i=xy−1d⇀1,i,b⇀2,i=d⇀2,i,b⇀3=d⇀3,b⇀4=d⇀4∀i∈U,b⇀1,i∗=xyd⇀1,i∗,b⇀2,i∗=d⇀2,i∗,b⇀3∗=d⇀3∗,b⇀4∗=d⇀4∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. The SF components b⇀5,i,b⇀6 and b⇀5,i∗,b⇀6∗ which will be set later can supply fresh parameters to randomize the ciphertext and the private key, respectively.
In line 1, the TPDH assumption adversaryC is given the public parameters of the system and its challenge T. In line 7, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A. In line 15, A requests for the private key K1,i,K2∀i∈A1. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, C outputs A’s guess as its own guess. By analysing this game, if T=gxyz, then the power vector becomes xyzriz−1Φix−1y−1rid⇀5,i∗=Φib⇀5,i∗ as needed for the nominal SF key. Alternatively, this power vector is distributed as random multiples of b⇀5,i∗, which is required for an ephemeral SF key. Hence, when T=gxyz, then C has successfully simulated GamekN, and if T is a random group element, then C has successfully simulated GamekT. Therefore, C can capitalize on A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against the TPDH assumption.Lemma 5.
Under the subspace assumption, no PPT adversary can achieve a non-negligible advantage in distinguishing betweenGamekT and GameK for any k from 1 to Q.Proof:.
This proof is closely indistinguishable to the proof of Lemma1, except that C adds additional terms of gΦib⇀1,i∗+a3b⇀1,i∗ attached to K1,i, respectively, for the k-th key (in which it picks a3∈ℤp randomly). This guarantees that if the τ3 terms are not present, the k-th key will be correctly distributed as SF key.Lemma 6.
Under the subspace assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGameQ and Gamefinal.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GameQ from Gamefinal, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption asB,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating GameQ and Gamefinal is described as follows:(1)
G,p,gd⇀3,gd⇀4,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←ℤp(3.2)
letΓ0=T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1=T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀i∈U;(3.3)
returnC←b?Γb;(3.4)(4)
EncGen(4.1)
letμ1,μ2,y1,y2←$ℤp;(4.2)
letU1,i←gμ1γ1d⇀1,i+μ2γ2d⇀2,i+μ3γ3d⇀5,i,U2←gμ1γ1d⇀3+μ2γ2d⇀4+μ3d⇀6∀i∈U;(4.3)
returnU1,i,U2(4.4)(5)
α1,α2←ℤp(6)
let pp=G,p,gd1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,eg,gα1s1δ,eg,gα2s2δ;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀3←$ℤpt′(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(8.7)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8)
letd⇀2,i∗⟶d⇀5,i∗ωi;(8.9)
letd⇀5,i∗⟶d⇀1,i∗Φi;(8.10)
letK2=T2;(8.11)
fori=1toQ1;(8.11.1)
writeK1,i=gλiy1∗b⇀1,i∗T1,i;(8.11.2)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,s˜3←$ℤp;(13)
lets˜1←μ1,s˜2←μ2,s˜3←μ3;(14)
letC0=msgb⋅e6U1,i,T1,i;(15)
letC2=U2;(16)
foritoS∗(16.1)
guideS∗⊭A1;(16.2)
writeC1,i=d⇀1,iμ1d⇀2,iμ2;(16.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(17)(18)
b=b′;
To simulate eitherGameQ or Gamefinal, algorithm C sets the bases for the construction as(27)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈Ub⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ητ1,α2=βτ2. Then, C produces(28)eg,gα1s1δ=∏i=1ne6T1,i,gγ1d⇀1,iα1,eg,gα2s2δ=∏i=1ne6T1,i,gγ2d⇀2,iα2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute set S∗ does not satisfy the access structure which is enforced by the guard. Eventually, C outputs A’s guess as its own guess. By analysing this game, if the exponent of T1,i is equal to γ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗ and U1,i=μ1γ1b⇀1,i+μ2γ2b⇀2,i, then we have(29)∏i=1ne6U1,i,T1,i=eg,gα1s1+α2s2δ,and hence we have a well-distributed SF encryption of msgb∗, as required in GameQ. In this instance, Γ0 and Γ0∗ are used in generating the challenge ciphertext. If instead the power of T1,i=γ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗, then we have(30)∏i=1ne6U1,i,T1,i=eg,gα1s1+α2s2+α3s3δ.
As long as theτ3 term remains hidden in the SF ciphertext, it provides a blinding factor required for encryption of random message in the Gamefinal. Consequently, C can capitalize on A’s non-negligible advantage in distinguishing between these games to attain a non-negligible advantage against the subspace assumption.


## 5.1. SF Ciphertext

To create this ciphertext for a set of attributesS, firstly, we execute the normal encryption algorithm in equation (15). The ciphertext is made up of the following components: C0,C1,i,∀i∈S,C2. Then, we pick random valuesB,B∗←$Dualℤp3,δS3∈ℤp and multiply C1,i by gs3b⇀5,i. Also, we multiply C2 by gs3b⇀6. The other component of the ciphertext stays unaltered as shown below.(18)ct=C0=msg⋅eg,gα1s1δ+α2s2δ,C1,i=gs1y1b⇀1,i+s2y2b⇀2,igs3b⇀5,iC2=gs1b⇀3+s2b⇀4gs3b⇀6,∀i∈S.


## 5.2. SF Keys

To generate these keys for anmspM,ρ, we first execute the normal key generation algorithm in equation (14) to get a normal key made up of the following components of K1,i∈ρi,K2. We then pick random secret values a3,α3∈ℤp and a random vector v=r1,…,rt∈ℤpt and set the index r1=α3. We produce shares for the secret as Φi=Mi⋅vT, where Mi is the row vector in M with the label ρi. The SF key is output as(19)skA=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗⋅gΦib⇀5∗,i+a3b⇀5∗,iK2=ga1r1b⇀3∗+a2r2b⇀4∗⋅ga3b⇀6∗,i∈ρi.Recall that we do not put a partition on a simulator with a nominal SF key. Therefore, the nominal SF key correlates correctly with the SF ciphertext to allow decryption, regardless of the presence or absence of SF components. This happens because the share of the secretα3 in the SF space is zero.


## 5.3. Ephemeral SF Keys

These keys are indistinguishable to nominal keys, with the exception that SF components attach to eitherK1,i or K2 which is now being randomized (which prevent accurate SF ciphertext decryption). Concretely, to create an ephemeral SF key for the access matrix M, we first execute the normal key generation algorithm in equation (15) to get a normal key made up of the following components of K1,i∈ρi, K2. We then pick random secret values a3,a4, a5,α3∈ℤp and a random vector v=r1,…,rt∈ℤpt and set the index r1=α3. Note that value of the secret α3 in the SF space is zero. We produce shares for the secret as Φi=Mi⋅vT, where Mi is the row vector in M with the label ρi. The SF key is output as(20)skA=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗⋅gωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗⋅ga4Φib⇀5∗,i+a3b⇀5,i∗K2=ga1r1b⇀3∗+a2r2b⇀4∗⋅ga3b⇀6∗,i∈ρi.


## 5.4. Proof Structure

The hybrid proof is executed over a series of games. DenotingQ as the total number of key requested by adversary, we define the series of games as follows: Gamereal is the real security game as in Section 3 (see Definition 10). In Gamek, the ciphertext submitted to the adversary is SF, as are the first k keys. The rest of the keys are normal. GamekN is similar to Gamek, besides the fact that the k-th key delivered to the adversary is nominal SF key. The first k−1 keys are SF, whereas the rest of the keys are normal. GamekT is similar to Gamek, besides the fact that the k-th key delivered to the adversary is an ephemeral SF. The first k−1 keys are SF, whereas the rest of the keys are normal. Gamefinal is analogous to GameQ, besides the fact that the SF ciphertext delivered to the adversary is encryption of random message.The layout of our hybrid argument will be as follows. Firstly, we move fromGamereal to Game0, then to Game1, next to Game2, and so on. Eventually, we get to GameQ, where all of the keys and the ciphertext delivered to the adversary are SF. Then, we move to Gamefinal and this completes our security proof since any adversary in the final game has negligible advantage. The transition from Gamereal to Game0 and from GameQ to Gamefinal is not complicated and can be done with the help of the computational assumptions. However, the transition from GameK−1 to Gamek is a bit complicated and requires other steps. For these steps, we will consider making transition between two phases. Phase 1 is when the adversary requests a challenge ciphertext after obtaining the secret key. In phase 2, the adversary requests a secret key after obtaining the challenge ciphertext. Therefore, in order to get from Gamek−1 to Gamek, we will transition first from Gamek−1 to GamekN, then to GamekT, and finally to Gamek. We let Q1 represent the number of queries in phase 1, and we will tackle this transition independently for k≤Q1 and k≥Q1. The security proof for phase 1 queries and phase 2 queries is similar to the selective security proof in the KP-ABE settings and CP-ABE settings, respectively.Lemma 1.
Under the subspace assumption, no PPT adversary can achieve a non-negligible advantage in distinguishingGamereal and Game0.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing Gamereal from Game0, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption as B,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating Gamereal and Game0 is described as follows :(1)
G,p,gd⇀3,gd⇀4,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ←C;(2)
b←$0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←$ℤp;(3.2)
letΓ0:=T1,i⟵gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2⟵gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1:=T1,i⟵gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2⟵gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀iU;(3.3)
returnC←b?Γb;(3.4)(4)
α1,α2←$ℤp;(5)
α1←ηα1,α2←βα2;(6)
let pp=G,p,gd⇀1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,e6gd⇀1,i,gηd⇀1,i∗α1,e6gd⇀2,i,gβd⇀2,i∗α2;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀2←$ℤpt;(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(8.7)
letK2=T2;(8.8)
fori=1toQ1;(8.8.1)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8.2)
letd⇀2,i∗⟶d⇀2,i∗ωi;(8.8.3)
letd⇀5,i∗⟶d⇀5,i∗Φi;(8.8.4)
writeK1,i=gy1∗ηd⇀1,i∗T1,i;(8.8.5)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,y1,y2←$ℤp(13)
letC0=msgb.eg,gα˜1s˜1δ+α˜2s˜2δ;(14)
letC2=gs1b⇀3+s4b⇀4=gd⇀3s˜1⋅gd⇀4s˜2;(15)
foritoS∗(15.1)
guideS∗⊭A1;(15.2)
Writegs1y1b⇀1,i+s2y2b⇀2,i=gd⇀1,is˜1+γ1gd⇀2,is˜2+γ2;(15.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(16)(17)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(17.1)
y1∗,α3,←$ℤp;(17.2)
Cpp,α1,α2,α3,Γ0,Γ1(17.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(17.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(17.5)
letωi←M1T∗v⇀2, where α2 is the secret;(17.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(17.7)
letK2=T2;(17.8)
fori=Q1+1toQ(17.8.1)
guard (A1⊭S∗)(17.8.2)
letd⇀1,i∗⟶d⇀1,i∗λi;(17.8.3)
letd⇀2,i∗⟶d⇀2,i∗ωi;(17.8.4)
letd⇀5,i∗⟶d⇀5,i∗Φi;(17.8.5)
writeK1,i=gy1∗d⇀1,iT1,i(17.8.6)
OutputK1,i,K2∀i∈A1⟶A(18)
b=b′
To simulate eitherGamereal or Game0, Algorithm C sets the bases for the construction as(21)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈U,b⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseD∗,D,D0∗,D0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ηα1,α2=βα2. Then, C produces(22)eg,gα1s1=e6gd⇀1,i,gηd⇀1,i∗α1,eg,gα2s2δ=e6gd⇀2,i,gβηd⇀2,i∗α2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure which is enforced by the guard. In line 17, A requests for the private key K1,i,K2∀i∈A1 for the second time. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, CoutputsA’s guess as its own guess. By analysing this game, when the τ3 terms are absent in the private key, then C correctly simulates GameReal. In this instance, Γ0 is used in generating the private key. When τ3 terms are present, then C correctly simulates Game0. In this case, Γ1 is used in generating the private key. Therefore, C can capitalize on algorithm A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against subspace assumption.Lemma 2.
Under the subspace assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamek−1 and GamekN for any k from 1 to Q.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GameK−1 from GamekN, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption as B,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating Gamek−1 and GamekN is described as follows:(1)
G,p,gd⇀3,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ,U←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←$ℤp;(3.2)
letΓ0≔T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1≔T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀i∈U;(3.3)
returnC←b?Γb;(3.4)(4)
EncGen(4.1)
letμ1,μ2,μ3,y1,y2←$ℤp;(4.2)
letΓ0∗=U1,i←gμ1γ1b⇀1,i+μ2γ2b⇀2,i,U2←gμ1γ1b⇀3+μ2γ2b⇀4Γ1∗=U1,i←gμ1γ1b⇀1,i+μ2γ2b⇀2,i+μ3b⇀5,i,U2←gμ1γ1b⇀3+μ2γ2b⇀4+μ3b⇀6∀i∈U;(4.3)
returnC←b?Γb∗;(4.4)(5)
α1,α2←$ℤp;(6)
let pp=G,p,gd1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,engd⇀1,gηd⇀1∗α1,engd⇀1,gβd⇀2∗α2;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(8.7)
letK2=T2;(8.8)
fori=1toQ1(8.8.1)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8.2)
letd⇀2,i∗⟶d⇀1,i∗ωi;(8.8.3)
letd⇀2,i∗⟶d⇀1,i∗ωi;(8.8.4)
writeK1,i=gλiy1∗b⇀1,i∗T1,i;(8.8.5)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,s˜3←$ℤp;(13)
lets˜1←μ1,s˜2←μ2,s˜3←μ3;(14)
letC0=msgb⋅eg,gα1s1δ+α2s2δ;(15)
letC2=U2;(16)
foritoS∗(16.1)
guideS∗⊭A1;(16.2)
writeC1,i=U1,i;(16.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(17)(18)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(18.1)
y1∗,α3,←$ℤp;(18.2)
Cpp,α1,α2,α3,Γ0,Γ1(18.3)
letv⇀1,v⇀2,v⇀3←ℤpt;(18.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(18.5)
letωi←M1T∗v⇀2, where α2 is the secret;(18.6)
letΦi←M1T∗v⇀3, where α3 is the secret;(18.7)
letK2=T2;(18.8)
fori=Q1+1toQ(18.8.1)
guard (A1⊭S∗)(18.8.2)
letd⇀1,i∗⟶d⇀1,i∗λi;(18.8.3)
letd⇀2,i∗⟶d⇀2,i∗ωi;(18.8.4)
letd⇀5,i∗⟶d⇀5,i∗Φi;(18.8.5)
writeK1,i=gy1∗d⇀1,iT1,i;(18.8.6)
OutputK1,i,K2∀i∈A1⟶A;(19)
b=b′;
To simulate eitherGameK−1 or GameKN, algorithm C sets the bases for the construction as(23)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈U,b⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseD∗,D,D0∗,D0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ηα1,α2=βα2. Then, C produces(24)eg,gα1s1=engd⇀1,gηd⇀1∗α1,eg,gα2s2δ=engd⇀1,gβηd⇀2∗α2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ,U. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure A1 which is enforced by the guard. In line 18, A requests for the private key K1,i,K2∀i∈A1 for the second time. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, C outputs A’s guess as its own guess. By analysing this game, when the extra components µ3b⇀5,i and µ3b⇀6 on C1,i and C2, respectively, are present, then the ciphertext is SF ciphertext (i.e., Γ∗=Γ1∗); otherwise, it is normal ciphertext (i.e., Γ∗=Γ0∗). Hence, C is capable to simulate normal and SF ciphertext. When the τ3 terms are absent in the private key, then C correctly simulates Gamek−1. In this instance, Γ0 is used in generating the private key. When τ3 terms are present, then C correctly simulates GamekN. In this case, Γ1 is used in generating the private key. Therefore, C can capitalize on algorithm A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against subspace assumption.Lemma 3.
Under the TPDH assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamekN and GamekT for any k from 1 to Q1 (note that these are phase 1 queries).Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GamekN from GamekT, then we will construct a PPT algorithm C to break the TPDH assumption. C gets g,gx,gy,gz where T is either gxyz or random element of G. Algorithm C simulates either GamekN from GamekT based on the nature of T. C picks a random dual orthonormal bases B,B∗,B0,B0∗ of 3 dimensions and B1,B1∗,…,BU,BU∗ of 6 dimensions n, all with the same value δ. The procedure for simulating GamekN and GamekT is described as follows:(1)
G,p,gb⇀3,gb⇀3∗,gb⇀4∗,gb⇀1,i,gb⇀2,i,gb⇀1,i∗,gb⇀2,i∗∀iU,Γ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letx,y,z←ℤp;(3.2)
letb⇀5,i∗←Dualℤp6,δ,b⇀6∗←Dualℤp3,δ;(3.3)
C←g,gx,gy,gz,T;(3.4)
letg,gx,gy,T;(3.5)
returnb⇀5,i∗∀iU,b⇀6∗;b?T←gxyz:T←G1;(3.6)(4)
α1,α2←$ℤp;(5)
let pp=G,p,gb1,i,gb⇀2,i,gb⇀3,gb⇀4∀i∈U,eg,gα1,eg,gα2;(6)
Outputpp⟶A;(7)
K1,Q1+1,…,Q,K2←AA1Q1+1,…,Q with;(7.1)
Cpp,α1,α2,α3,Γ0,Γ1(7.2)
y1∗,y2∗,α3,r1,r2,a1,a2,a3,a4←$ℤp;(7.3)
leta4=z−1,α3←0∈ℤp;(7.4)
letv⇀1,v⇀2,v⇀3←ℤpt;(7.5)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(7.6)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(7.7)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(7.8)
letK2=ga1r1b⇀3∗+a2r2b⇀4∗+a3cb⇀6∗;(7.9)
fori=Q1+1toQ(7.9.1)
writeK1,i=K1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗+ωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗TΦia4b⇀5,i∗+a3b⇀5,i∗;(7.9.2)
OutputK1,i,K2∀i∈A1⟶A;(8)(9)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(10)
Cpp,msg0∗,msg1∗,S∗(11)
lets˜1,s˜2,s˜3←$ℤp;(12)
letC0=msgb⋅eg,gα1s˜1δ+α2s˜2δ;(13)
letC2=gs˜1b⇀3+s˜2b⇀4+s˜3b⇀6;(14)
foritoS∗(14.1)
guideS∗⊭A1;(14.2)
letd⇀5,i←Dualℤp6,δ;(14.3)
writeC1,i=gs˜1y1b⇀1,i+s˜2y2b⇀2,i+s˜3b⇀5,i;(14.4)
OutputC0,C1,i,C2∀i∈S∗⟶A;(15)(16)
b=b′;
To simulate eitherGameKN or GameKT, algorithm C sets the bases for the construction as(25)b⇀1,i=d⇀1,i,b⇀2,i=d⇀2,i,b⇀3=d⇀3,b⇀4=d⇀4,b⇀5,i=d⇀5,i,b⇀6=d⇀6∀i∈U,b⇀1,i∗=d⇀1,i∗,b⇀2,i∗=d⇀2,i∗,b⇀3∗=d⇀3∗,b⇀4∗=d⇀4∗,b⇀5,i∗=xy−1d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. The SF components b⇀5,i,b⇀6 and b⇀5,i∗,b⇀6∗ can supply fresh parameters to randomize the ciphertext and the private key, respectively.
In line 1, the TPDH assumption adversaryC is given the public parameters of the system and its challenge T. In line 7, A requests for its private keys, which C replies correctly to. In line 9, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute S∗ does not satisfy the access structure A1 which is enforced by the guard. Eventually, C outputs A’s guess as its own guess. By analysing this game, if T=gxyz, then the power vector becomes xyzxyz−1Φid⇀5,i∗=Φib⇀5,i∗ as needed for the nominal SF key. Alternatively, this power vector is distributed as random multiples of b⇀5,i∗, which is required for an ephemeral SF key. Hence, when T=gxyz, then C has successfully simulated GamekN, and if T is a random group element, then C has successfully simulated GamekT. Therefore, C can capitalize on A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against the TPDH assumption.Lemma 4.
Under the TPDH assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGamekN and GamekT for any k>Q1 (note that these are phase 2 queries).Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing Gamek1 and GamekN for some k such that Q1<k≤Q. We will construct a PPT algorithm C to break the TPDH assumption. C gets g,gx,gy,gz,T where T is either gxyz or a random element of B∗. C will simulate either GamekN or GamekT with algorithm A based on T. C picks a random dual orthonormal bases B,B∗,B0,B0∗ of 3 dimensions and B1,B1∗,…,BU,BU∗ of 6 dimensions, all with the same value δ. The procedure for simulating GamekN and GamekT is described as follows:(1)
G,p,gb⇀3,gb⇀3∗,gb⇀4∗,gb⇀1,i,gb⇀2,i,gb⇀1,i∗,gb⇀2,i∗∀iUΓ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letx,y,z,ri∀i∈s←$ℤp(3.2)
letb⇀5,i∗←$Dualℤp6,δ,b⇀6∗←$Dualℤp3,δ;(3.3)
b⇀5,i∗⟶x−1rid⇀5,i∗∀i∈S;(3.4)
C←g,gx,gy,gz,T;(3.5)
letg,gx,gy,T;(3.6)
returnri,b⇀5,i∗∀iU,b⇀6∗;b?T←gxyz:T←G1;(3.7)(4)
α1,α2←ℤp;(5)
let pp=G,p,gb1,i,gb⇀2,i,gb⇀3,gb⇀4∀i∈U,eg,gα1,eg,gα2;(6)
Outputpp⟶A(7)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(8)
Cpp,msg0∗,msg1∗,S∗(9)
lets˜1,s˜2,s˜3←$ℤp;(10)
letC0=msgb⋅eg,gα1s˜1δ+α2s˜2δ;(11)
letb⇀6←Dualℤp3,δ;(12)
letC2=gs˜1b⇀3+s˜2b⇀4+s˜3b⇀6;(13)
foritoS∗(13.1)
letb⇀5,i←Dualℤp6,δ;(13.2)
writeC1,i=gs˜1y1b⇀1,i+s˜2y2b⇀2,i+s˜3b⇀5,i;(13.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(14)(15)
K1,Q1+1,…,Q1,…,Q1,K2←AA1Q1+1,…,Q with;(15.1)
Cpp,α1,α2,ri,b⇀5,i∗,b⇀6∗,T(15.2)
y1∗,y2∗,α3,r1,r2,a4←$ℤp′(15.3)
letα3←0∈ℤp;(15.4)
Let∑i=1nri⟶ψ,θi←1/ri⋅1/ψ∀i∈S∗;(15.5)
leta4←y−1,z=ψ;(15.6)
letv⇀1,v⇀2,v⇀3←$ℤpt(15.7)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(15.8)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(15.9)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(15.10)
guideS∗⊭A1;(15.11)
letK2=ga1r1b⇀3∗+a2r2b⇀4∗+a3cb⇀6∗;(15.12)
fori=Q1+1toQ(15.12.1)
letΦi˜←Φiθi;(15.12.2)
writeK1,i=gλiy1∗b⇀1,i∗+a1r1y1∗b⇀1,i∗+ωiy2∗b⇀2,i∗+a2r2y2∗b⇀2,i∗Ta4Φi˜b⇀5,i∗+a3b⇀5,i∗;(15.12.3)
OutputK1,i,K2∀i∈A1⟶A;(16)
b=b′;
To simulate eitherGamekN or GamekT, algorithm C sets the bases for the construction as(26)b⇀1,i=xy−1d⇀1,i,b⇀2,i=d⇀2,i,b⇀3=d⇀3,b⇀4=d⇀4∀i∈U,b⇀1,i∗=xyd⇀1,i∗,b⇀2,i∗=d⇀2,i∗,b⇀3∗=d⇀3∗,b⇀4∗=d⇀4∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. The SF components b⇀5,i,b⇀6 and b⇀5,i∗,b⇀6∗ which will be set later can supply fresh parameters to randomize the ciphertext and the private key, respectively.
In line 1, the TPDH assumption adversaryC is given the public parameters of the system and its challenge T. In line 7, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A. In line 15, A requests for the private key K1,i,K2∀i∈A1. C outputs the correct private key to A with the restriction that the access structure A1 does not satisfy the attribute set S∗ of the previously queried ciphertext. Eventually, C outputs A’s guess as its own guess. By analysing this game, if T=gxyz, then the power vector becomes xyzriz−1Φix−1y−1rid⇀5,i∗=Φib⇀5,i∗ as needed for the nominal SF key. Alternatively, this power vector is distributed as random multiples of b⇀5,i∗, which is required for an ephemeral SF key. Hence, when T=gxyz, then C has successfully simulated GamekN, and if T is a random group element, then C has successfully simulated GamekT. Therefore, C can capitalize on A’s non-negligible advantage in distinguishing between these two games to obtain a non-negligible advantage against the TPDH assumption.Lemma 5.
Under the subspace assumption, no PPT adversary can achieve a non-negligible advantage in distinguishing betweenGamekT and GameK for any k from 1 to Q.Proof:.
This proof is closely indistinguishable to the proof of Lemma1, except that C adds additional terms of gΦib⇀1,i∗+a3b⇀1,i∗ attached to K1,i, respectively, for the k-th key (in which it picks a3∈ℤp randomly). This guarantees that if the τ3 terms are not present, the k-th key will be correctly distributed as SF key.Lemma 6.
Under the subspace assumption, no PPT adversary can have a non-negligible advantage in distinguishing betweenGameQ and Gamefinal.Proof:.
Suppose a PPT algorithmA achieves a non-negligible advantage in distinguishing GameQ from Gamefinal, then we will construct a PPT algorithm C to break the subspace assumption. We will set the parameters ni=3,m=U+2,ki=1, for two values of i and ni=6,ki=2 for the remaining values of i in the subspace assumption. To correctly align the assumption notation with our scheme notation, we hereby designate the bases of the assumption asB,B∗,B0,B0∗∈Dualℤp3,δ and B1,B1∗,…,BU,BU∗∈Dualℤp6,δ. We will exclude the µ3 term because it is not applicable here. The procedure for simulating GameQ and Gamefinal is described as follows:(1)
G,p,gd⇀3,gd⇀4,gηd⇀3∗,gβd⇀4∗,gd⇀1,i,gd⇀2,i,gηd⇀1,i∗,gβd⇀2,i∗∀iU,Γ←C;(2)
b←0,1;(3)
KeyGenGen(3.1)
letγ1∗,γ2∗,τ1,τ2,τ3←ℤp(3.2)
letΓ0=T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗,Γ1=T1,i←gγ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗,T2←gγ1∗τ1ηd⇀3∗+γ2∗τ2βd⇀4∗+τ3d⇀6∗∀i∈U;(3.3)
returnC←b?Γb;(3.4)(4)
EncGen(4.1)
letμ1,μ2,y1,y2←$ℤp;(4.2)
letU1,i←gμ1γ1d⇀1,i+μ2γ2d⇀2,i+μ3γ3d⇀5,i,U2←gμ1γ1d⇀3+μ2γ2d⇀4+μ3d⇀6∀i∈U;(4.3)
returnU1,i,U2(4.4)(5)
α1,α2←ℤp(6)
let pp=G,p,gd1,i,gd⇀2,i,gd⇀3,gd⇀4∀i∈U,eg,gα1s1δ,eg,gα2s2δ;(7)
Outputpp⟶A;(8)
K1,1,…,Q1,K2←AA11,…,Q1 with;(8.1)
y1∗,α3,←$ℤp;(8.2)
Cpp,α1,α2,α3,Γ0,Γ1(8.3)
letv⇀1,v⇀2,v⇀3←$ℤpt′(8.4)
letλi←M1T∗v⇀1, where α1 is the secret, A1≡M1;(8.5)
letωi←M1T∗v⇀2, where α2 is the secret, A1≡M1;(8.6)
letΦi←M1T∗v⇀3, where α3 is the secret, A1≡M1;(8.7)
letd⇀1,i∗⟶d⇀1,i∗λi;(8.8)
letd⇀2,i∗⟶d⇀5,i∗ωi;(8.9)
letd⇀5,i∗⟶d⇀1,i∗Φi;(8.10)
letK2=T2;(8.11)
fori=1toQ1;(8.11.1)
writeK1,i=gλiy1∗b⇀1,i∗T1,i;(8.11.2)
OutputK1,i,K2∀i∈A1⟶A;(9)(10)
C0,C1,i,C2←Amsg0∗,msg1∗,S∗ with;(11)
Cpp,msg0∗,msg1∗,S∗(12)
lets˜1,s˜2,s˜3←$ℤp;(13)
lets˜1←μ1,s˜2←μ2,s˜3←μ3;(14)
letC0=msgb⋅e6U1,i,T1,i;(15)
letC2=U2;(16)
foritoS∗(16.1)
guideS∗⊭A1;(16.2)
writeC1,i=d⇀1,iμ1d⇀2,iμ2;(16.3)
OutputC0,C1,i,C2∀i∈S∗⟶A;(17)(18)
b=b′;
To simulate eitherGameQ or Gamefinal, algorithm C sets the bases for the construction as(27)b⇀1,i=ηb⇀1,i,b⇀2,i=βb⇀2,i,b⇀3=ηb⇀3,b⇀4=βb⇀4,b⇀5,i=b⇀5,i,b⇀6=b⇀6∀i∈Ub⇀1,i∗=η−1d⇀1,i∗,b⇀2,i∗=β−1d⇀2,i∗,b⇀3∗=η−1d⇀3∗,b⇀4∗=β−1d⇀4∗,b⇀5,i∗=d⇀5,i∗,b⇀6∗=d⇀6∗∀i∈U.
We assert that these are well distributed becauseB∗,B,B0∗,B0, etc., are chosen randomly up to sharing the same value δ. Implicitly, C selects α1,α2∈ℤp and sets α1=ητ1,α2=βτ2. Then, C produces(28)eg,gα1s1δ=∏i=1ne6T1,i,gγ1d⇀1,iα1,eg,gα2s2δ=∏i=1ne6T1,i,gγ2d⇀2,iα2.
In line 1, the subspace assumption adversaryC is given the public parameters of the system and its challenge Γ. In line 8, A requests for its private keys, which C replies correctly to. In line 10, A sends two messages msg0∗,msg1∗ of the same length with the attribute S∗ to C and requests for the challenge ciphertext. In response, C outputs the correct ciphertext tuple C0,C1,i,C2∀i∈S∗ to A with the restriction that the attribute set S∗ does not satisfy the access structure which is enforced by the guard. Eventually, C outputs A’s guess as its own guess. By analysing this game, if the exponent of T1,i is equal to γ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗ and U1,i=μ1γ1b⇀1,i+μ2γ2b⇀2,i, then we have(29)∏i=1ne6U1,i,T1,i=eg,gα1s1+α2s2δ,and hence we have a well-distributed SF encryption of msgb∗, as required in GameQ. In this instance, Γ0 and Γ0∗ are used in generating the challenge ciphertext. If instead the power of T1,i=γ1∗τ1ηd⇀1,i∗+γ2∗τ2βd⇀2,i∗+τ3d⇀3,i∗, then we have(30)∏i=1ne6U1,i,T1,i=eg,gα1s1+α2s2+α3s3δ.
As long as theτ3 term remains hidden in the SF ciphertext, it provides a blinding factor required for encryption of random message in the Gamefinal. Consequently, C can capitalize on A’s non-negligible advantage in distinguishing between these games to attain a non-negligible advantage against the subspace assumption.


## 6. Implementation and Evaluation

We implemented the automation proofs of our KP-ABE scheme in AutoG&P [37]. In all cases, the proof is discovered semiautomatically, with the lines of codes which involve manual hand-tuning steps. The implementation was executed on Intel i7 personal laptop with 2.2 GHz CPU and 8 GB RAM running on macOS High Sierra 10.13.6. The proof-generation time for all the hybrid games of our scheme (i.e. Gamereal⟶Game0,Gamek−1⟶GamekN,GamekN⟶GamekT,GamekT⟶Gamek,GameQ⟶Gamefinal took 498 ms.Additionally, we use python cryptographic library known as charm-crypto 0.43 [38] to implement our KP-ABE scheme and the ABE scheme by Lewko and Waters [3] (Lw), which are the only schemes which support dual vector subspace assumption and thus whose functionalities are close to our scheme among the known ABE schemes. We used SS512 elliptic curve with 512 bit base field and SHA-3 hash function. We set the number of attribute as 10 and increase by 10 number of attributes each time. The benchmarks of the experiments are shown in Figures 2–4.Figure 2
Computation cost for key generation.Figure 3
Computation cost for encryption.Figure 4
Computation cost for decryption.As can be inferred from Figures2 and 4, the computation cost for key generation and encryption algorithms increases with the increment in the size of attributes. Our scheme has less computation overhead as compared to Lw scheme. This is because our scheme has less exponentiation of computation of the group elements. Also, our scheme has less decryption computation cost which can be inferred from Figure 4. This is as a result of less number of pairing operations in decryption as compared with Lw scheme.


### 6.1. Theoretical Comparison

We provide theoretical comparisons with some KP-ABE schemes which are shown in Tables2–5. To enable us to make comparison with JL [26] scheme which uses asymmetric elliptic curve, we adopted the approach in [39] to convert Lw [3], GSW [31], and our scheme from the symmetric setting unto asymmetric setting without having to compute isomorphisms between the source groups. We use “MNT159” asymmetric curve with 159 bit base field from charm-crypto python library. Table 6 gives the cost of the computation operations. The parameters are set as follows:(i)
m: the number of attributes.(ii)
d: the maximum of multiple use of attributes.(iii)
n′: the number of distinct labels n′≤n.(iv)
n,nt,nf: the number of inputs and non-negated and negated inputs to a policy, respectively n=nt+nf.(v)
I,It,If: the number of attributes and non-negated and negated attributes in decryption, respectively (I=It+If).(vi)
n1: the number of rows of a matrix for span programs.Table 2
Comparison of key generation algorithm in KP-ABE schemes.
SchemesKey generationG1G2ExpHashExpHashOurs46n1+23———Lw [3]46n1+43———JL [26]15nt+18nf12n′3d—GSW [31]n1———Table 3
Comparison of encryption algorithm in KP-ABE schemes.
SchemesEncryptionG1G2ExpHashExpHashOurs——26m+23—Lw [3]——46m+43—JL [26]12m12m3—GSW [31]——m—Table 4
Comparison of decryption algorithm in KP-ABE schemes.G1,G2,GT
SchemesDecryptionExponentiationPairingG1G2GTOurs———6I+3Lw [3]———6I+9JL [26]9Ifd——6dGSW [31]———IWe omit the multiplication cost in the groups (G1,G2,GT) as they are insignificant when comparing with exponentiation and pairing.Table 5
Size comparison of KP-ABE schemes.
SchemesKey sizeCiphertext sizeG1G2G1G2Ours6n1+3——6m+3Lw [3]6n1+6——6m+6JL [26]3nt+2nf3d3m3GSW [31]—n1—mTable 6
Running times of time-consuming operations.
OperationTiming (seconds)G1-exponentiation0.011842G2-exponentiation0.037413GT-exponentiation0.017396Hashing toG10.012839Pairing0.041798As can be deduced from Tables2–4, GSW is the most efficient scheme. However, it does not support the multiuse and adaptive security properties. Although JL supports multiuse of attributes in the access policy, the computation cost of key generation increases with multiuse of attribute by the factor of d. However, since our scheme and Lw use the selective technique in generation of either the ciphertext or the key, the scheme performance is not affected by the multiuse of attribute. In terms of computation cost of decryption, the number of pairing operations and exponentiation increases with the factor of d in JL scheme when attributes are reused multiple times. However, our scheme and Lw scheme are not affected by multiuse of attribute. The computation cost only increases when there is an increment in the size of attributes.From Table6, we can infer that GSW has the least size of key and ciphertext. However, it does not support multiuse of attributes. Although JL supports multiuse of attributes, the size of the ciphertext increases by the factor of d. While the key and ciphertext sizes of Lw and our scheme are not affected by multiuse of attributes, comparatively our scheme has lesser key and ciphertext sizes than Lw scheme.


## 6.1. Theoretical Comparison

We provide theoretical comparisons with some KP-ABE schemes which are shown in Tables2–5. To enable us to make comparison with JL [26] scheme which uses asymmetric elliptic curve, we adopted the approach in [39] to convert Lw [3], GSW [31], and our scheme from the symmetric setting unto asymmetric setting without having to compute isomorphisms between the source groups. We use “MNT159” asymmetric curve with 159 bit base field from charm-crypto python library. Table 6 gives the cost of the computation operations. The parameters are set as follows:(i)
m: the number of attributes.(ii)
d: the maximum of multiple use of attributes.(iii)
n′: the number of distinct labels n′≤n.(iv)
n,nt,nf: the number of inputs and non-negated and negated inputs to a policy, respectively n=nt+nf.(v)
I,It,If: the number of attributes and non-negated and negated attributes in decryption, respectively (I=It+If).(vi)
n1: the number of rows of a matrix for span programs.Table 2
Comparison of key generation algorithm in KP-ABE schemes.
SchemesKey generationG1G2ExpHashExpHashOurs46n1+23———Lw [3]46n1+43———JL [26]15nt+18nf12n′3d—GSW [31]n1———Table 3
Comparison of encryption algorithm in KP-ABE schemes.
SchemesEncryptionG1G2ExpHashExpHashOurs——26m+23—Lw [3]——46m+43—JL [26]12m12m3—GSW [31]——m—Table 4
Comparison of decryption algorithm in KP-ABE schemes.G1,G2,GT
SchemesDecryptionExponentiationPairingG1G2GTOurs———6I+3Lw [3]———6I+9JL [26]9Ifd——6dGSW [31]———IWe omit the multiplication cost in the groups (G1,G2,GT) as they are insignificant when comparing with exponentiation and pairing.Table 5
Size comparison of KP-ABE schemes.
SchemesKey sizeCiphertext sizeG1G2G1G2Ours6n1+3——6m+3Lw [3]6n1+6——6m+6JL [26]3nt+2nf3d3m3GSW [31]—n1—mTable 6
Running times of time-consuming operations.
OperationTiming (seconds)G1-exponentiation0.011842G2-exponentiation0.037413GT-exponentiation0.017396Hashing toG10.012839Pairing0.041798As can be deduced from Tables2–4, GSW is the most efficient scheme. However, it does not support the multiuse and adaptive security properties. Although JL supports multiuse of attributes in the access policy, the computation cost of key generation increases with multiuse of attribute by the factor of d. However, since our scheme and Lw use the selective technique in generation of either the ciphertext or the key, the scheme performance is not affected by the multiuse of attribute. In terms of computation cost of decryption, the number of pairing operations and exponentiation increases with the factor of d in JL scheme when attributes are reused multiple times. However, our scheme and Lw scheme are not affected by multiuse of attribute. The computation cost only increases when there is an increment in the size of attributes.From Table6, we can infer that GSW has the least size of key and ciphertext. However, it does not support multiuse of attributes. Although JL supports multiuse of attributes, the size of the ciphertext increases by the factor of d. While the key and ciphertext sizes of Lw and our scheme are not affected by multiuse of attributes, comparatively our scheme has lesser key and ciphertext sizes than Lw scheme.


## 7. Conclusions

In the prime-order bilinear groups, we have introduced KP-ABE scheme which is fully secure and supports arbitrary usage of attributes in the access policy. This scheme attains full security under DLIN assumption and three-party assumption. This work removes high security loss that is involved in the reuse of attributes and enables the nonrestricted use of attributes. Our key point is inspired by the idea that the information-theoretical steps of the former dual system proof give the adversary excessive ground as if the computational arguments would be enough. So, we revived the earlier selective proofing techniques within the framework of dual system of encryption to gain enough ground to achieve full security proof.



---

*Source: 8869057-2020-11-29.xml*