Attributebased Proxy Reencryption with a Constant Number of Pairing Operations
 Author: Seo Hwa Jeong, Kim Howon
 Organization: Seo Hwa Jeong; Kim Howon
 Publish: Journal of information and communication convergence engineering Volume 10, Issue1, p53~60, 31 March 2012

ABSTRACT
Attributebased 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 attributebased proxy reencryption (ABPRE) scheme was proposed, which combines traditional proxy reencryption with ABE, so a user is able to empower designated users to decrypt the reencrypted 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 reencryption , Key delegation

I. INTRODUCTION
Identitybased cryptography encrypts the message with the user’s identity including the name and email address. An identitybased encryption (IBE) scheme can restrict an authority to indicate the identity of the recipient [1, 2]. Attributebased 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 (KPABE) in which each private key is associated with an access structure [4]. The other scheme is the ciphertext policy ABE (CPABE), in which a ciphertext is associated with an access structure [57]. The attributebased proxy reencryption scheme (ABPRE) extends traditional proxy reencryption to its attributebased 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 CPABE 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 computationbased 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 reencrypt the ciphertext using a rekey. Detailed relationships are shown in Fig. 1. First
U_{1} generates the ciphertextC_{1} , which can be decrypted withU_{1} ’s attributes. One day,U_{1} is absent, but we need to read the data fromC_{1} . In this case,U_{1} will store the reencrypted ciphertext with attributes that represent the specific recipient or groups into a proxyserver. After that,U_{2} can access to the proxyserver and then gain the reencrypted data.> A. ABPRE Model
The ABPRE scheme is illustrated in [8, 10]. An ABPRE scheme is comprised of six steps including SETUP, KEYGEN, REGEN, ENC, REENC, and DEC.
SETUP: The setup algorithm takes no input other than the implicit security parameter. It outputs the public parameters
pp and a master keymk .KEYGEN (
S, mk ): The key generation algorithm takes as input the master key^{mk} and a set of attributesS that describe the key. It outputs a private key .usk REGEN (
usk ,AS ): The rekey generation algorithm takes as input the secret key and access structureusk . It outputs a rekeyAS rk .ENC (
m ,AS ): The encryption algorithm takes as input the public parameterspp , a messagem , and an access structure over the universe of attributes. The algorithm will encryptAS m and produce a ciphertextC 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 REENC (
rk ,C ): The reencryption algorithm takes as input the rekeyrk and a ciphertextC . First the algorithm checks the index set inrk . Ifrk satisfies the access structure ofC , it outputs a reencrypted ciphertextC ' ; otherwise, it rejects the rekey.DEC (
pp , C , ): The decryption algorithm takes as input the public parametersusk pp , a ciphertextC , which contains an access policy , and a private keyAS , which is a private key for a setusk S of attributes. If the setS of attributes satisfies the access structure then the algorithm will decrypt the ciphertext and return a messageAS m .III. PRELIMINARIES
In this section, some definitions which are the basis of attributebased encryption schemes, including our scheme, are presented.
> A. Bilinear Groups
Definition 1. Bilinear groups and a bilinear map are defined as follows:G andG_{T} are finite cyclic groups of prime orderp . e is an efficiently computable bilinear map or pairinge : G ×G →G_{T} , with the following properties;Bilinearity: For any
g,h ∈ G , anda,b ∈ Z_{p} , we havee(g^{a} ,h^{b}) = e(g,h)^{a·b} .Nondegeneracy:
e(g,g) ≠ 1.Note that
e(*,*) is symmetric sincee(g^{a} ,g^{b}) = e(g,g)^{a·b} = e(g^{b} ,g^{a}) .> B. Complexity Assumptions
Definition 2. Complex Triple DiffieHellman (CTDH) problem. Lete : G ×G → G_{T} be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersn,a,b,c,d ,R ∈ Z_{p} . Given a tupleas inputs, output
g^{abc} .Definition 3. Augment DiffieHellman (ADH) problem. Lete : G × G → G_{T} be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersa,b ∈ Z_{p} . Given a tupleas inputs, output
g^{ab} .Definition 4. The CTDH assumption holds inG if no probabilistic polynomial time adversary is able to outputg^{abc} fromwith nonnegligible advantage, where random numbers
n,a,b,c,d ,R ∈ Z_{p} and generatorg ∈ 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
, we could select
R + nd = 1,R = ab,b = c and outputsg^{Rc} from the CTDH oracle with inputsThe CTDH problem is the basis of the master key security in our scheme.
Definition 5. Augment decisional bilinear DiffieHellman (ADBDH) problem. Lete : G × G → G_{T} be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersa,b,c ∈ Z_{p} . Given a tupleas inputs, output 1 if
Z = e(g,g)^{abc} ; otherwise, output 0.Definition 6. The ADBDH assumption holds inG if no probabilistic polynomial time adversary is able to distinguish the tupleswith nonnegligible advantage, where
a,b,c,z ∈ Z_{p} and a generatorg ∈ G are chosen independently and uniformly at random.IV. ATTRIBUTEBASED PROXY REENCRYPTION 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∧(+d_{i} , ？d_{i} )_{i ∈τ} , which are the positive attribute and the negative attribute, respectively. Any user receives a secret key associated with an attribute setS ⊆ τ 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 (1
^{k} ) : A bilinear groupG of prime orderp ,with bilinear mape : G × G → G_{T} is generated. Next, it selects elementsk ,y ,z ,t_{i} (1≤i ≤ 3n ) inZ_{p} and two generatorsg,h ofG at random. LetY := e(g,h)^{y} andT_{i} := g^{ti} for each 1≤i ≤ 3n . The public parameterpp includesThe master key
mk is< k ,y ,z ,{t_{i}}_{1≤ i ≤ 3n} > .KGEN(
S,mk ) : LetS denote an index set of attributes. It chooses a randomr_{1},...,r_{n} from theZ_{p} and setsr = r_{1} + r_{2} + ... + r_{n} . It computesand for each
= {1,2,...,i ∈ N (Nn }) :(D_{i,1} = h^{ri} )_{i∈N} . This outputs a user’s secret keyENC(
m, ) : LetAS denote an access structure. To encrypt a messageAS m ∈ G_{T} , it selects a randoms ∈ Z_{p} and computesFor
i ∈ N : if+d_{i} appears as ,AS C_{i} = T^{s}_{i} ; ifd_{i} appears as ,AS C_{i} = T^{s}_{n+i} ; otherwise,C_{i} = T^{s}_{2n+i} . It outputsRKGEN(
) : Letusk ,AS ' denote a valid secret key consisting ofusk and let
denote an access structure. It selects a randomAS 'd ∈ Z_{p} and setFor
i ∈ N D^{'}_{i ,1} =D_{i ,1} ·h^{d} ; C^{'} is the ciphertext of ？ under the access structure .AS 'It outputs
REENC(
rk ,C ) : Letrk denote a valid rekey consisting ofand
C denote a wellformed ciphertextThis step checks whether
S satisfies ; if not, output ┻ ; otherwise, forAS i ∈ N :+d_{i} appears inAS ,？d_{i} appears inAS ,Otherwise,
It computes
and
Next it computes
E = e(C,D^{T} ) = e(g,h)^{(n·d+r)(k·s·z)} It then computes
It outputs a reencrypted ciphertext
Note that
C_{re} can be reencrypted iteratively. Thus we would obtainwhere
C'' is obtained from the REENC algorithm with the input of anotherrk^{'} andC^{'} . The size of the ciphertext and reencryption times increase linearly.DEC (
C, ) : Letusk denote a valid secret keyusk . It checks whether
S satisfies ; if not, it outputs ┻; otherwise, decrypt.AS If
C is an original wellformed ciphertext consisting of, for
i ∈ N :+d_{i} appears inAS ,？d_{i} appears inAS ,Otherwise,
It computes
and
Next it computes
E = e(C,D^{T} ) = e(g,h)^{k·r·s·z} It outputs
Otherwise, if
C is a reencrypted wellformed ciphertext consisting of, then it decrypts
C^{'} usingusk and obtains ？ =g^{d} . Then it outputsOtherwise, if is a multitime reencrypted wellformed 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,G_{T} ) , the ABPRE scheme ensures selectivestructure chosen plaintext secure in the standard model.Proof: In this section, we show that SSCPAABPRE meets the requirements in terms of the ADBDH assumption.
We suppose that an adversary wins the SSCPAABPRE game with a nonnegligible advantage ε . A simulator
S can be constructed to distinguishD_{adbdh} fromD_{rand} with the nonnegligible advantageWe first suppose the challenger set the groups
G andG_{T} with bilinear mape and a generatorg . The challenger randomly selects a side of a fair coinc , withoutS ’s intervention. Ifc = true the challenger sets< g,A,B,C,B^{'} ,Z >∈ D_{adbdh} ; otherwise it sets .' ,Z >∈ D_{rand} Init:
S receives a challenge access structure ^{*} , and namesAS I _{+}^{*} ,I _{？}^{*} the index set of positive and negative attributes, respectively. ThenS choosesx ,y ,α_{i} ,β_{i} ,γ_{i} at random fromZ_{p} fori ∈ N and generates the public keyY = e(A,B )^{y} . ThenS 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 oracleO_{kg} , the rekey generation oracleO_{rkg} , and the reencryption oracleO_{ree} .A makes several queries to theO_{kg} with an index setI_{q} . According to the security game, ifI_{q} satisfies ^{*} , it outputs ┻.AS Otherwise,
S queriesfrom the oracle and outputs
usk .A makes a query toO_{rkg} with an index setI_{q} and an access structureAS . According to the security game, ifI_{q} satisfiesAS ^{*} , it outputs ┻. Otherwise,S submitsI_{q} toO_{kg} and obtains a secret key.
S executes the following procedure:It selects a random
d ∈ Z_{p} and setFor
i ∈ N D^{'}_{ i ,1} = D_{i ,1} ·h^{d} , it outputs, in which
C' is the ciphertext of ？ under the access structureAS '.A makes a query toO_{ree} with an index setI_{q} , an access structureAS' , and a ciphertextAccording to the security game, if
I_{q} satisfiesAS ^{*} , it outputs ┻. IfI_{q} does not satisfyAS , it outputs ┻. ThenS submits (I_{q} ,AS' ) to the rekey generation oracle and obtains.
S usesrk to reencrypt the ciphertextC . Fori ∈ N :+d_{i} appears inAS ,？d_{i} appears inAS ,Otherwise,
.It computes
, and
Next it computes
E = e(C,D^{T} ) = e(g,h)^{(n·d+r)(k·s·z)} Finally, it computes
It outputs a reencrypted ciphertext
Challenge:
A submits two equal messagesM_{0} andM_{1} in length.S produces a challenge ciphertext:Phase 2: Same procedure as Phase 1.
Guess: A tuple was given from
D_{adbdh} whenS outputsc' = 1 andA gives a correct guessμ' = μ ;otherwise a tuple was given fromD_{rand} whenS outputsc' = 0 .According to [3], the advantage of the simulator to output a correct
v ' = v isTheorem 2: If the CTDH assumption holds in
G , G_{T} ,then the ABPRE scheme has master key security.Proof: The simulator
S receives a tupleand a challenge index set
I * . To outputg^{abc} , the simulatorS does as follows:Init:
S choosesα_{i} ,β_{i} ,γ_{i} at random fromZ_{p} fori ∈ N and generates the public key and setY = e(g,h)^{ab} = e(g_{b} ,g_{3}) . Then it computes public keys as follows:i ∈ I^{*} , T_{i} = g^{αi} ,T_{n+i} = g_{b}^{βi} ,T_{2n+i} = g_{b}^{γi} ;i ？ I^{*} , T_{i} = g_{b}^{αi} ,T_{n+i} = g^{βi} ,T_{2n+i} = g_{b}^{γi} ;S outputs public parameterKey generation oracle:
A makes a query to the key generation oracle with an index setI_{q} ⊆ N whereI_{q} ≠ I * . An index j must belong to the following conditions ((j ∈ I_{q} ) _{∧} (j ？ I * ) or (j ？ I_{q} ) _{∧} (j ∈ I * ) ). For this reason,we just analyze the case of (j ∈ I_{q} ) _{∧} (j ？ I * ).For every
i ∈N,S choosesr'_{i} ∈ Z_{p} at random and implicitly setsr_{i} in the following ways:r_{i} =br'_{i} (i ≠ j ; ),r_{j} =ab + br'_{i} (otherwise).Denote
and
For
i ∈ I_{q} , i ≠ j : ifi ∈ I* else
i ？ I* For
i ？ I_{q} , i ≠ j : if i ∈ I* ,else
i ？ I* For,
i = j : ,It outputs a secret key
Rekey generation oracle:
A makes a query to the key generation oracle with an index setI_{q} ⊆N and access structureAS , ifI_{q} ≠ I* . , obtainusk fromKGEN (I_{q} ) and generaterk =RKGEN (usk ,AS ) ; elseI_{q} =I *.Select
j ∈ I* andat random for each
i ∈ N ￦ {j };Implicitly set
and
for
i ∈ N ;Compute
for
i ∈ N :If
i ≠ j, i ∈ I* ,Else if
i ≠ j, i ？ I* Else if
Output
where
C is the ciphertext ofg_{d} · g^{t} under the access structureAS .Reencryption oracle:
A makes a query to the key generation oracle with an index setI_{q} ⊆N and access structure: ifI_{q} ≠I * . , obtainrk fromRKGEN (usk ,AS') and generateC' = REENC(rk ,C) ; elseI_{q} =I* .For
i ∈ N : +
d_{i} appears inAS ,where
 ？
d_{i} appears inAS ,where
 Otherwise,
where
It outputs a secret key
usk ^{*} forI ^{*} includingIf it is a valid secret key,
usk ^{*} satisfies the following equation:The decryption oracle is straightforward, since the secret key and rekey could be correctly generated from the Key generation and Rekey generation oracle.
It outputs
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 andkC_{e} denote the ktimes calculation over groupG and pairing, respectively. Letu = {att_{1},att_{2},...,att_{n}} be the set of attributes.Let
r_{1} andr_{2} be a set of attributes associated with the ciphertext and a set of attributes associated with the secret key, respectively. Let
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 ABPREbased schemes. Therefore, we can empower designated users with the capability of decryption. Our security assumption is based on CTDH and ADBDH. This provides a selectivestructure 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 CPABE 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 reencrypted with a new access structure. The scheme can be adapted to various applications including email 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).

[Fig 1.] The attributebased proxy reencryption scheme system.

[Table 1.] Computational time of each algorithm

[Table 2.] Some properties of attributebased encryption schemes