Attribute-based Proxy Re-encryption with a Constant Number of Pairing Operations

  • cc icon
  • 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.


  • KEYWORD

    Attribute based encryption , Proxy re-encryption , Key delegation

  • 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.

      >  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

    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

    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

    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

    image

    , we could select R + nd = 1,R = ab,b = c and outputs gRc from the CTDH oracle with inputs

    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

    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

    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 +di appears in AS , then i ∈ S ;

    If ?di appears in AS , then i ? S .

      >  C. Main Construction

    SETUP (1k ) : 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 ≤ 3n) in Zp and two generators g,h of G at random. Let Y := e(g,h)y and Ti := gti for each 1≤ i ≤ 3n . The public parameter pp includes

    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

    image

    and for each i ∈ N(N = {1,2,...,n}) : (Di,1 = hri )i∈N . This outputs a user’s secret key

    image

    ENC(m,AS) : Let AS denote an access structure. To encrypt a message m ∈ GT , it selects a random s ∈ Zp and computes

    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

    image

    RKGEN(usk, AS') : Let usk denote a valid secret key consisting of

    image

    and let AS' denote an access structure. It selects a random d ∈ Zp and set

    image

    For i ∈ N D'i ,1 =Di ,1 ·hd ; C' is the ciphertext of ? under the access structure AS' .

    It outputs

    image

    REENC(rk ,C) : Let rk denote a valid re-key consisting of

    image

    and C denote a well-formed ciphertext

    image

    This step checks whether S satisfies AS ; if not, output ┻ ; otherwise, for i ∈ N :

    +di appears in AS ,

    image

    ?di appears in AS ,

    image

    Otherwise,

    image

    It computes

    image
    image

    and

    image

    Next it computes E = e(C,DT ) = e(g,h)(n·d+r)(k·s·z)

    It then computes

    image

    It outputs a re-encrypted ciphertext

    image

    Note that Cre can be re-encrypted iteratively. Thus we would obtain

    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

    image

    . It checks whether S satisfies AS ; if not, it outputs ┻; otherwise, decrypt.

    If C is an original well-formed ciphertext consisting of

    image

    , for i ∈ N :

    +di appears in AS ,

    image

    ?di appears in AS ,

    image

    Otherwise,

    image

    It computes

    image
    image

    and

    image

    Next it computes E = e(C,DT ) = e(g,h)k·r·s·z

    It outputs

    image

    Otherwise, if C is a re-encrypted well-formed ciphertext consisting of

    image

    , then it decrypts C' using usk and obtains ? = gd . Then it outputs

    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

    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

    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

    image

    . S executes the following procedure:

    It selects a random d ∈ Zp and set

    image

    For i ∈ N D' i ,1 = Di ,1 ·hd , it outputs

    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

    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

    image

    . S uses rk to re-encrypt the ciphertext C . For i ∈ N :

    +di appears in AS,

    image

    ?di appears in AS,

    image

    Otherwise,

    image

    .It computes

    image
    image

    , and

    image

    Next it computes E = e(C,DT ) = e(g,h)(n·d+r)(k·s·z)

    Finally, it computes

    image

    It outputs a re-encrypted ciphertext

    image

    Challenge: A submits two equal messages M0 and M1 in length. S produces a challenge ciphertext:

    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

    image
    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

    image
    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

    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

    image

    and

    image

    For i ∈ Iq , i ≠ j : if i ∈ I*

    image

    else i ? I*

    image

    For i ? Iq , i ≠ j : if i ∈ I* ,

    image

    else i ? I*

    image

    For, i = j : ,

    image

    It outputs a secret key

    image

    Rekey generation oracle: A makes a query to the key generation oracle with an index set IqN 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

    image

    at random for each i ∈ N ₩ {j};

    Implicitly set

    image

    and

    image

    for i ∈ N;

    Compute

    image

    for i ∈ N :

    If i ≠ j, i ∈ I* ,

    image

    Else if i ≠ j, i ? I*

    image

    Else if

    image

    Output

    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 IqN and access structure: if IqI *. , obtain rk from RKGEN (usk ,AS') and generate C' = REENC(rk ,C) ; else Iq = I*.

    -For i ∈ N :

    - +di appears in AS,

    image

    where

    image

    - ?di appears in AS ,

    image

    where

    image

    - Otherwise,

    image

    where

    image

    It outputs a secret key usk* for I* including

    image

    If it is a valid secret key, usk* satisfies the following equation:

    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

    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.

    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

    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).

  • 1. Boneh D, Franklin M. K 2001 “Identity-based encryption fromthe weil pairing” [Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology] P.213-229 google
  • 2. Boyen X, Waters B 2006 “Anonymous hierarchical identity-basedencryption” [Proceedings of the 26th Annual International Cryptology Conference on Advances in Cryptology] P.290-307 google
  • 3. Sahai A, Waters B 2005 “Fuzzy identity-based encryption” [Proceedings of the 24th Annual International Conference onTheory and Applications of Cryptographic Techniques] P.457-473 google
  • 4. 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] P.89-98 google
  • 5. Cheung L, Newport C 2007 “Provably secure ciphertext policy ABE” [Proceedings of the 14th ACM conference on Computer and Communications Security] P.456-465 google
  • 6. 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] P.579-591 google
  • 7. Bethencourt J, Sahai A, Waters B 2007 “Ciphertext-policy attribute-based encryption” [Proceedings of the 2007 IEEE Symposium on Security and Privacy] P.321-334 google
  • 8. 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] P.276-286 google
  • 9. 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] P.13-23 google
  • 10. Canetti R, Hohenberger S 2007 “Chosen-ciphertext secure proxyre-encryption” [Proceedings of the 14th ACM Conference o nComputer and Communications Security] P.185-194 google
  • 11. 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] P.111-129 google
  • 12. 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] P.53-70 google
  • [Fig 1.] The attribute-based proxy re-encryption scheme system.
    The attribute-based proxy re-encryption scheme system.
  • [Table 1.] Computational time of each algorithm
    Computational time of each algorithm
  • [Table 2.] Some properties of attribute-based encryption schemes
    Some properties of attribute-based encryption schemes