Advanced
Attribute-based Proxy Re-encryption with a Constant Number of Pairing Operations
Attribute-based Proxy Re-encryption with a Constant Number of Pairing Operations
Journal of information and communication convergence engineering. 2012. Mar, 10(1): 53-60
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/bync/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : September 23, 2011
  • Accepted : November 14, 2011
  • Published : March 31, 2012
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hwa Jeong Seo

Abstract
Attribute-based encryption (ABE) is an encryption scheme in which the user is able to decrypt a ciphertext with associated attributes. However, the scheme does not offer the capability of decryption to others when the user is offline. For this reason, the attribute-based proxy re-encryption (ABPRE) scheme was proposed, which combines traditional proxy re-encryption with ABE, so a user is able to empower designated users to decrypt the re-encrypted ciphertext with the associated attributes of designated users. However, previous ABPRE schemes demands a number of pairing operations that imply huge computational overhead. To reduce the number of pairing operations, we reduce the pairing operations with exponent operations. This paper provides a novel approach to an ABPRE scheme with constant pairing operation latency.
Keywords
I. INTRODUCTION
Identity-based cryptography encrypts the message with the user’s identity including the name and e-mail address. An identity-based encryption (IBE) scheme can restrict an authority to indicate the identity of the recipient [1 , 2] . Attribute-based encryption (ABE) was published by Sahai and Waters [3] . Unlike IBE, the message is encrypted with attributes, such as gender, age, and affiliation, so ABE schemes can designate the recipients by assigning common attributes of others. ABE consists of two policies. The first is the key policy ABE (KP-ABE) in which each private key is associated with an access structure [4] . The other scheme is the ciphertext policy ABE (CP-ABE), in which a ciphertext is associated with an access structure [5 - 7] . The attribute-based proxy re-encryption scheme (ABPRE) extends traditional proxy re-encryption to its attribute-based counterpart. Therefore, the capability of delegation is transferred to the designated users [8] . However, the previous ABPRE does not provide a constant length of message and number of pairing operations. Recently, a constant ciphertext length based CP-ABE was proposed by Emura et al. [9] . The computation cost and ciphertext length were reduced significantly compared to previous papers. However, the encryption scheme over ABPRE has not been proposed yet. For this reason, in the present paper, we propose a new constant computation-based ABPRE. The scheme utilizes the capability of delegation with constant pairing operations.
The rest of this paper is organized as follows. In section II, we describe ABPRE. In section III, preliminaries such as bilinear map and complexity assumptions are introduced to support the construction and the security proof. In section IV, our new ABPRE scheme is introduced and then we analyze security model and computation performance. Finally the conclusion is drawn in section V.
II. DEFINITION OF ABPRE
In ABPRE, a user can re-encrypt the ciphertext using a re-key. Detailed relationships are shown in Fig. 1 . First U1 generates the ciphertext C1 , which can be decrypted with U1 ’s attributes. One day, U1 is absent, but we need to read the data from C1 . In this case, U1 will store the re-encrypted ciphertext with attributes that represent the specific recipient or groups into a proxy-server. After that, U2 can access to the proxy-server and then gain the re-encrypted data.
PPT Slide
Lager Image
The attribute-based proxy re-encryption scheme system.
- A. ABPRE Model
The ABPRE scheme is illustrated in [8 , 10] . An ABPRE scheme is comprised of six steps including SETUP, KEYGEN, RE-GEN, ENC, RE-ENC, and DEC.
SETUP: The setup algorithm takes no input other than the implicit security parameter. It outputs the public parameters pp and a master key mk .
KEYGEN ( S, mk ): The key generation algorithm takes as input the master key mk and a set of attributes S that describe the key. It outputs a private key usk .
RE-GEN ( usk , AS ): The re-key generation algorithm takes as input the secret key usk and access structure AS . It outputs a re-key rk .
ENC ( m , AS ): The encryption algorithm takes as input the public parameters pp , a message m , and an access structure AS over the universe of attributes. The algorithm will encrypt m and produce a ciphertext C such that only a user that possesses a set of attributes that satisfies the access structure will be able to decrypt the message. The ciphertext implicitly contains AS .
RE-ENC ( rk ,C ): The re-encryption algorithm takes as input the re-key rk and a ciphertext C . First the algorithm checks the index set in rk . If rk satisfies the access structure of C , it outputs a re-encrypted ciphertext C ' ; otherwise, it rejects the re-key.
DEC ( pp , C , usk ): The decryption algorithm takes as input the public parameters pp , a ciphertext C , which contains an access policy AS , and a private key usk , which is a private key for a set S of attributes. If the set S of attributes satisfies the access structure AS then the algorithm will decrypt the ciphertext and return a message m .
III. PRELIMINARIES
In this section, some definitions which are the basis of attribute-based encryption schemes, including our scheme, are presented.
- A. Bilinear Groups
Definition 1. Bilinear groups and a bilinear map are defined as follows: G and GT are finite cyclic groups of prime order p . e is an efficiently computable bilinear map or pairing e : G ×G →GT , with the following properties;
Bilinearity: For any g,h ∈ G , and a,b ∈ Zp , we have e(ga ,hb) = e(g,h)a・b .
Non-degeneracy: e(g,g) ≠ 1.
Note that e(*,*) is symmetric since e(ga ,gb) = e(g,g)a・b = e(gb ,ga) .
- B. Complexity Assumptions
Definition 2. Complex Triple Diffie-Hellman (CTDH) problem. Let e : G ×G → GT be a bilinear map, where G has prime order p and g is a generator of G , random numbers n,a,b,c,d ,R ∈ Zp . Given a tuple
PPT Slide
Lager Image
as inputs, output gabc .
Definition 3. Augment Diffie-Hellman (ADH) problem. Let e : G × G → GT be a bilinear map, where G has prime order p and g is a generator of G , random numbers a,b ∈ Zp . Given a tuple
PPT Slide
Lager Image
as inputs, output gab .
Definition 4. The CTDH assumption holds in G if no probabilistic polynomial time adversary is able to output gabc from
PPT Slide
Lager Image
with non-negligible advantage, where random numbers n,a,b,c,d ,R ∈ Zp and generator g ∈ G are chosen independently and uniformly at random.
The CTDH problem is more difficult than the ADH problem; if given the input of the ADH problem
PPT Slide
Lager Image
, we could select R + nd = 1, R = ab,b = c and outputs gRc from the CTDH oracle with inputs
PPT Slide
Lager Image
The CTDH problem is the basis of the master key security in our scheme.
Definition 5. Augment decisional bilinear Diffie-Hellman (ADBDH) problem. Let e : G × G → GT be a bilinear map, where G has prime order p and g is a generator of G , random numbers a,b,c ∈ Zp . Given a tuple
PPT Slide
Lager Image
as inputs, output 1 if Z = e(g,g)abc ; otherwise, output 0.
Definition 6. The ADBDH assumption holds in G if no probabilistic polynomial time adversary is able to distinguish the tuples
PPT Slide
Lager Image
with non-negligible advantage, where a,b,c,z ∈ Zp and a generator g ∈ G are chosen independently and uniformly at random.
IV. ATTRIBUTE-BASED PROXY RE-ENCRYPTION WITH CONSTANT PAIRING OPERATION LATENCY
- A. Our Techniques
We adapt a constant number of pairing operations to a previous ABPRE scheme [8] . Whenever the attribute is decided in the scheme, to reflect the attributes, we need to compute the pairing operation with its designated attributes. To reduce the number of pairing operations, we reduce the pairing operation by using an exponential operation which can easily calculate the summation of the exponent. Therefore, we calculate the exponent and then compute the pairing operation just once.
- B. Satisfying an Access Structure
In this scheme we consider the access structure consisting of AND gates between positive and negative attributes. Denote the index set of all the attributes as τ .The access structure is represented as ∧(+di , −di )i ∈τ , which are the positive attribute and the negative attribute, respectively. Any user receives a secret key associated with an attribute set S ⊆ τ from the authority. The users can decrypt the ciphertext, if the following conditions of the attribute are met:
  • If+diappears inAS, theni ∈ S;
  • If−diappears inAS, theni ∉ S.
- C. Main Construction
SETUP (1 k ) : A bilinear group G of prime order p ,with bilinear map e : G × G → GT is generated. Next, it selects elements k ,y ,z ,ti (1≤ i ≤ 3 n ) in Zp and two generators g,h of G at random. Let Y := e(g,h)y and Ti := gti for each 1≤ i ≤ 3 n . The public parameter pp includes
PPT Slide
Lager Image
The master key mk is < k ,y ,z ,{ti}1≤ i ≤ 3n > .
KGEN( S,mk ) : Let S denote an index set of attributes. It chooses a random r1,...,rn from the Zp and sets r = r1 + r2 + ... + rn . It computes
PPT Slide
Lager Image
and for each i ∈ N(N = {1,2,..., n }) : (Di,1 = hri )i∈N . This outputs a user’s secret key
PPT Slide
Lager Image
ENC( m,AS ) : Let AS denote an access structure. To encrypt a message m ∈ GT , it selects a random s ∈ Zp and computes
PPT Slide
Lager Image
For i ∈ N : if +di appears as AS , Ci = Tsi ; if -di appears as AS , Ci = Tsn+i ; otherwise, Ci = Ts2n+i . It outputs
PPT Slide
Lager Image
RKGEN( usk, AS' ) : Let usk denote a valid secret key consisting of
PPT Slide
Lager Image
and let AS' denote an access structure. It selects a random d ∈ Zp and set
PPT Slide
Lager Image
For i ∈ N D'i ,1 =Di ,1 ・hd ; C' is the ciphertext of ℑ under the access structure AS' .
It outputs
PPT Slide
Lager Image
REENC( rk ,C ) : Let rk denote a valid re-key consisting of
PPT Slide
Lager Image
and C denote a well-formed ciphertext
PPT Slide
Lager Image
This step checks whether S satisfies AS ; if not, output ┻ ; otherwise, for i ∈ N :
+di appears in AS ,
PPT Slide
Lager Image
−di appears in AS ,
PPT Slide
Lager Image
Otherwise,
PPT Slide
Lager Image
It computes
PPT Slide
Lager Image
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Next it computes E = e(C,DT ) = e(g,h)(n・d+r)(k・s・z)
It then computes
PPT Slide
Lager Image
It outputs a re-encrypted ciphertext
PPT Slide
Lager Image
Note that Cre can be re-encrypted iteratively. Thus we would obtain
PPT Slide
Lager Image
where C'' is obtained from the REENC algorithm with the input of another rk' and C' . The size of the ciphertext and re-encryption times increase linearly.
DEC ( C,usk ) : Let usk denote a valid secret key
PPT Slide
Lager Image
. It checks whether S satisfies AS ; if not, it outputs ┻; otherwise, decrypt.
If C is an original well-formed ciphertext consisting of
PPT Slide
Lager Image
, for i ∈ N :
+di appears in AS ,
PPT Slide
Lager Image
−di appears in AS ,
PPT Slide
Lager Image
Otherwise,
PPT Slide
Lager Image
It computes
PPT Slide
Lager Image
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Next it computes E = e(C,DT ) = e(g,h)k・r・s・z
It outputs
PPT Slide
Lager Image
Otherwise, if C is a re-encrypted well-formed ciphertext consisting of
PPT Slide
Lager Image
, then it decrypts C' using usk and obtains ℑ = gd . Then it outputs
PPT Slide
Lager Image
Otherwise, if is a multi-time re-encrypted well-formed ciphertext, then decryption is similar with the above phases.
- D. Security Proof for ABPRE
Since our scheme is an expansion of a previous ABPRE scheme in [8] , the security proof is based on previous proof in [8] and we also extend it to our scheme.
Theorem 1: When the ADBDH assumption holds in ( G,GT ) , the ABPRE scheme ensures selective-structure chosen plaintext secure in the standard model.
Proof: In this section, we show that SS-CPA-ABPRE meets the requirements in terms of the ADBDH assumption.
We suppose that an adversary wins the SS-CPA-ABPRE game with a non-negligible advantage ε . A simulator S can be constructed to distinguish Dadbdh from Drand with the non-negligible advantage
PPT Slide
Lager Image
We first suppose the challenger set the groups G and GT with bilinear map e and a generator g . The challenger randomly selects a side of a fair coin c , without S ’s intervention. If c = true the challenger sets < g,A,B,C,B' ,Z >∈ Dadbdh ; otherwise it sets ' ,Z >∈ Drand .
Init: S receives a challenge access structure AS * , and names I + * , I * the index set of positive and negative attributes, respectively. Then S chooses x ,y ,αiii at random from Zp for i ∈ N and generates the public key Y = e(A,B )y . Then S outputs the public parameters as follows:
  • i ∈ I+*, Ti= gαi,Tn+i= Bβi,T2n+i= Bγi;
  • i ∈ I−*, Ti= Bαi,Tn+i= gβi,T2n+i= Bγi;
  • Otherwise ,Ti= Bαi,Tn+i= Bβi,T2n+i= gγi.
Phase 1: An adversary A makes several queries to the key generation oracle Okg , the re-key generation oracle Orkg , and the re-encryption oracle Oree .
A makes several queries to the Okg with an index set Iq . According to the security game, if Iq satisfies AS * , it outputs ┻.
Otherwise, S queries
PPT Slide
Lager Image
from the oracle and outputs usk .
A makes a query to Orkg with an index set Iq and an access structure AS . According to the security game, if Iq satisfies AS * , it outputs ┻. Otherwise, S submits Iq to Okg and obtains a secret key
PPT Slide
Lager Image
. S executes the following procedure:
It selects a random d ∈ Zp and set
PPT Slide
Lager Image
For i ∈ N D' i ,1 = Di ,1 ・hd , it outputs
PPT Slide
Lager Image
, in which C' is the ciphertext of ℑ under the access structure AS '.
A makes a query to Oree with an index set Iq , an access structure AS' , and a ciphertext
PPT Slide
Lager Image
According to the security game, if Iq satisfies AS * , it outputs ┻. If Iq does not satisfy AS , it outputs ┻. Then S submits ( Iq , AS' ) to the re-key generation oracle and obtains
PPT Slide
Lager Image
. S uses rk to re-encrypt the ciphertext C . For i ∈ N :
+di appears in AS ,
PPT Slide
Lager Image
−di appears in AS ,
PPT Slide
Lager Image
Otherwise,
PPT Slide
Lager Image
.It computes
PPT Slide
Lager Image
PPT Slide
Lager Image
, and
PPT Slide
Lager Image
Next it computes E = e(C,DT ) = e(g,h)(n・d+r)(k・s・z)
Finally, it computes
PPT Slide
Lager Image
It outputs a re-encrypted ciphertext
PPT Slide
Lager Image
Challenge: A submits two equal messages M0 and M1 in length. S produces a challenge ciphertext:
PPT Slide
Lager Image
Phase 2: Same procedure as Phase 1.
Guess: A tuple was given from Dadbdh when S outputs c' = 1 and A gives a correct guess μ' = μ ;otherwise a tuple was given from Drand when S outputs c' = 0 .
According to [3] , the advantage of the simulator to output a correct v ' = v is
PPT Slide
Lager Image
PPT Slide
Lager Image
Theorem 2: If the CTDH assumption holds in G , GT ,then the ABPRE scheme has master key security.
Proof: The simulator S receives a tuple
PPT Slide
Lager Image
PPT Slide
Lager Image
and a challenge index set I * . To output gabc , the simulator S does as follows:
Init: S chooses αiii at random from Zp for i ∈ N and generates the public key and set Y = e(g,h)ab = e(gb ,g3) . Then it computes public keys as follows:
i ∈ I* , Ti = gαi ,Tn+i = gbβi ,T2n+i = gbγi ;
i ∉ I* , Ti = gbαi ,Tn+i = gβi ,T2n+i = gbγi ;
S outputs public parameter
PPT Slide
Lager Image
Key generation oracle: A makes a query to the key generation oracle with an index set Iq ⊆ N where Iq ≠ I * . An index j must belong to the following conditions (( j ∈ Iq ) ( j ∉ I * ) or ( j ∉ Iq ) ( j ∈ I * ) ). For this reason,we just analyze the case of ( j ∈ Iq ) ( j ∉ I * ).
For every i ∈N,S chooses r'i ∈ Zp at random and implicitly sets ri in the following ways: ri = br'i ( i ≠ j ; ), rj = ab + br'i (otherwise).
Denote
PPT Slide
Lager Image
and
PPT Slide
Lager Image
For i ∈ Iq , i ≠ j : if i ∈ I*
PPT Slide
Lager Image
else i ∉ I*
PPT Slide
Lager Image
For i ∉ Iq , i ≠ j : if i ∈ I* ,
PPT Slide
Lager Image
else i ∉ I*
PPT Slide
Lager Image
For, i = j : ,
PPT Slide
Lager Image
It outputs a secret key
PPT Slide
Lager Image
Rekey generation oracle: A makes a query to the key generation oracle with an index set Iq N and access structure AS , if Iq ≠ I* . , obtain usk from KGEN ( Iq ) and generate rk = RKGEN ( usk ,AS ) ; else Iq = I *.
Select j ∈ I* and
PPT Slide
Lager Image
at random for each i ∈ N ₩ { j };
Implicitly set
PPT Slide
Lager Image
and
PPT Slide
Lager Image
for i ∈ N ;
Compute
PPT Slide
Lager Image
for i ∈ N :
If i ≠ j, i ∈ I* ,
PPT Slide
Lager Image
Else if i ≠ j, i ∉ I*
PPT Slide
Lager Image
Else if
PPT Slide
Lager Image
Output
PPT Slide
Lager Image
where C is the ciphertext of gd · gt under the access structure AS .
Re-encryption oracle: A makes a query to the key generation oracle with an index set Iq N and access structure: if Iq I * . , obtain rk from RKGEN (usk ,AS') and generate C' = REENC(rk ,C) ; else Iq = I* .
-For i ∈ N :
- + di appears in AS ,
PPT Slide
Lager Image
where
Computational time of each algorithm
PPT Slide
Lager Image
Computational time of each algorithm
PPT Slide
Lager Image
- − di appears in AS ,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
- Otherwise,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
It outputs a secret key usk * for I * including
PPT Slide
Lager Image
If it is a valid secret key, usk * satisfies the following equation:
PPT Slide
Lager Image
The decryption oracle is straightforward, since the secret key and re-key could be correctly generated from the Key generation and Rekey generation oracle.
It outputs
PPT Slide
Lager Image
and solves the CTDH problem.
- E. Evaluation
Majority of ABE or ABPRE schemes require computing a number of pairing operations to generate the ciphertext depending on unique attributes but the computational cost of a pairing operation is much higher than other operations. For this reason, a small number of pairing operations is important factor for efficient cryptography algorithms. In 2009, Emura et al. [9] presented a constant length of pairing operations in an ABE scheme. This scheme is the motivation of our algorithm. In our scheme, we propose an expansion algorithm of ABE, ABPRE maintaining a constant pairing operation. A comparison of computation complexity is illustrated in Table 1 .
The notation kG and kCe denote the k-times calculation over group G and pairing, respectively. Let u = {att1,att2,...,attn} be the set of attributes.
Some properties of attribute-based encryption schemesDBDH: decisional bilinear Diffie-Hellman, CTDH: complex triple Diffie-Hellman, ADBDH: augment decisional bilinear Diffie-Hellman.
PPT Slide
Lager Image
Some properties of attribute-based encryption schemes DBDH: decisional bilinear Diffie-Hellman, CTDH: complex triple Diffie-Hellman, ADBDH: augment decisional bilinear Diffie-Hellman.
Let r1 and r2 be a set of attributes associated with the ciphert
ext and a set of attributes associated with the secret key, respectively. Let
PPT Slide
Lager Image
be the total number of possible statements of attributes.
Comparison of some properties including policy anonymity, capability of delegation, and security assumption is illustrated in Table 2 . All schemes follow the ciphertext policy. Nishide et al. [11] scheme only provides recipient anonymity. Capability of delegation is a strong feature of ABPRE-based schemes. Therefore, we can empower designated users with the capability of decryption. Our security assumption is based on CTDH and ADBDH. This provides a selective-structure chosen to be plaintext secure and master key secure.
V. CONCLUSIONS
In the paper, we present the ABPRE with constant number of pairing operations. The scheme is motivated from previous CP-ABE by computing constant length and number of pairing operations. Compared to previous ones, our proposal has the strength of its capability of delegation. Through the feature, we can empower designated users to decrypt the ciphertext re-encrypted with a new access structure. The scheme can be adapted to various applications including e-mail forwarding and distributed file systems.
Future work includes how to implement the scheme efficiently in various environments such as traditional computing environments and embedded systems (wireless sensor network, near field communication, and radio frequency identification).
Acknowledgements
This work was supported for two years by a Pusan National University Research grant.
References
Boneh D , Franklin M. K 2001 “Identity-based encryption fromthe weil pairing” Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology Santa Barbara: CA 213 - 229
Boyen X , Waters B 2006 “Anonymous hierarchical identity-basedencryption” Proceedings of the 26th Annual International Cryptology Conference on Advances in Cryptology Santa Barbara: CA 290 - 307
Sahai A , Waters B 2005 “Fuzzy identity-based encryption” Proceedings of the 24th Annual International Conference onTheory and Applications of Cryptographic Techniques Aarhus, Denmark 457 - 473
Goyal V , Pandey O , Sahai A , Waters B 2006 “Attribute-based encryption for fine-grained access control of encrypted data” Proceedings of the 13th ACM Conference on Computer and Communications Security Alexandria: VA 89 - 98
Cheung L , Newport C 2007 “Provably secure ciphertext policy ABE” Proceedings of the 14th ACM conference on Computer and Communications Security Alexandria: VA 456 - 465
Goyal V , Jain A , Pandey O , Sahai A 2008 “Bounded ciphertext policy attribute based encryption” Proceedings of the 35th international colloquium on Automata, Languages and Programming Reykjavik Iceland 579 - 591
Bethencourt J , Sahai A , Waters B 2007 “Ciphertext-policy attribute-based encryption” Proceedings of the 2007 IEEE Symposium on Security and Privacy Oakland: CA 321 - 334
Liang X , Cao Z , Lin H , Shao J 2009 “Attribute based proxy re-encryptionwith delegating capabilities” Proceedings of the 4th International Symposium on Information, Computer, and Communications Security Sidney, Australia 276 - 286
Emura K , Miyaji A , Nomura A , Omote K , Soshi M 2009 “A ciphertext policy attribute-based encryption scheme with constant ciphertext length” Proceedings of the 5th International Conference on Information Security Practice and Experience Shaanxi, China 13 - 23
Canetti R , Hohenberger S 2007 “Chosen-ciphertext secure proxyre-encryption” Proceedings of the 14th ACM Conference o nComputer and Communications Security Alexandria: VA 185 - 194
Nishide T , Yoneyama K , Ohta K 2008 “Attribute-based encryption with partially hidden encryptor-specified access structures” Proceedings of the 6th International Conference on Applied Cryptography and Network Security New York: NY 111 - 129
Waters B 2008 “Ciphertext-policy attribute-based encryption: an expressive efficient and provably secure realization” Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography Conference on Public Key Cryptography Taormina, Italy 53 - 70