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.
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
[5

7]
. 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 ciphertext
C_{1}
, which can be decrypted with
U_{1}
’s attributes. One day,
U_{1}
is absent, but we need to read the data from
C_{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.
The attributebased proxy reencryption scheme system.
 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 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
.
REGEN (
usk
,
AS
): The rekey generation algorithm takes as input the secret key
usk
and access structure
AS
. It outputs a rekey
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
.
REENC (
rk ,C
): The reencryption algorithm takes as input the rekey
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 reencrypted ciphertext
C
' ; otherwise, it rejects the rekey.
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 attributebased encryption schemes, including our scheme, are presented.
 A. Bilinear Groups
Definition 1.
Bilinear groups and a bilinear map are defined as follows:
G
and
G_{T}
are finite cyclic groups of prime order
p . e
is an efficiently computable bilinear map or pairing
e : G ×G →G_{T}
, with the following properties;
Bilinearity: For any
g,h ∈ G
, and
a,b ∈ Z_{p}
, we have
e(g^{a} ,h^{b}) = e(g,h)^{a・b}
.
Nondegeneracy:
e(g,g)
≠ 1.
Note that
e(*,*)
is symmetric since
e(g^{a} ,g^{b}) = e(g,g)^{a・b} = e(g^{b} ,g^{a})
.
 B. Complexity Assumptions
Definition 2.
Complex Triple DiffieHellman (CTDH) problem. Let
e : G ×G → G_{T}
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 ∈ Z_{p}
. Given a tuple
as inputs, output
g^{abc}
.
Definition 3.
Augment DiffieHellman (ADH) problem. Let
e : G × G → G_{T}
be a bilinear map, where
G
has prime order
p
and
g
is a generator of
G
, random numbers
a,b ∈ Z_{p}
. Given a tuple
as inputs, output
g^{ab}
.
Definition 4.
The CTDH assumption holds in
G
if no probabilistic polynomial time adversary is able to output
g^{abc}
from
with nonnegligible advantage, where random numbers
n,a,b,c,d ,R ∈ Z_{p}
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
, we could select
R + nd
= 1,
R = ab,b = c
and outputs
g^{Rc}
from the CTDH oracle with inputs
The CTDH problem is the basis of the master key security in our scheme.
Definition 5.
Augment decisional bilinear DiffieHellman (ADBDH) problem. Let
e : G × G → G_{T}
be a bilinear map, where
G
has prime order
p
and
g
is a generator of
G
, random numbers
a,b,c ∈ Z_{p}
. Given a tuple
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
with nonnegligible advantage, where
a,b,c,z ∈ Z_{p}
and a generator
g ∈ 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 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 → G_{T}
is generated. Next, it selects elements
k ,y ,z ,t_{i}
(1≤
i
≤ 3
n
) in
Z_{p}
and two generators
g,h
of
G
at random. Let
Y := e(g,h)^{y}
and
T_{i} := g^{ti}
for each 1≤
i
≤ 3
n
. The public parameter
pp
includes
The master key
mk
is
< k ,y ,z ,{t_{i}}_{1≤ i ≤ 3n} >
.
KGEN(
S,mk
) : Let
S
denote an index set of attributes. It chooses a random
r_{1},...,r_{n}
from the
Z_{p}
and sets
r = r_{1} + r_{2} + ... + r_{n}
. It computes
and for each
i ∈ N(N
= {1,2,...,
n
}) :
(D_{i,1} = h^{ri} )_{i∈N}
. This outputs a user’s secret key
ENC(
m,AS
) : Let
AS
denote an access structure. To encrypt a message
m ∈ G_{T}
, it selects a random
s ∈ Z_{p}
and computes
For
i ∈ N
: if
+d_{i}
appears as
AS
,
C_{i} = T^{s}_{i}
; if
d_{i}
appears as
AS
,
C_{i} = T^{s}_{n+i}
; otherwise,
C_{i} = T^{s}_{2n+i}
. It outputs
RKGEN(
usk, AS'
) : Let
usk
denote a valid secret key consisting of
and let
AS'
denote an access structure. It selects a random
d ∈ Z_{p}
and set
For
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
) : Let
rk
denote a valid rekey consisting of
and
C
denote a wellformed ciphertext
This step checks whether
S
satisfies
AS
; if not, output ┻ ; otherwise, for
i ∈ N
:
+d_{i}
appears in
AS
,
−d_{i}
appears in
AS
,
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 obtain
where
C''
is obtained from the REENC algorithm with the input of another
rk^{'}
and
C^{'}
. The size of the ciphertext and reencryption times increase linearly.
DEC (
C,usk
) : Let
usk
denote a valid secret key
. It checks whether
S
satisfies
AS
; if not, it outputs ┻; otherwise, decrypt.
If
C
is an original wellformed ciphertext consisting of
, for
i ∈ N
:
+d_{i}
appears in
AS
,
−d_{i}
appears in
AS
,
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^{'}
using
usk
and obtains ℑ =
g^{d}
. Then it outputs
Otherwise, 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 distinguish
D_{adbdh}
from
D_{rand}
with the nonnegligible advantage
We first suppose the challenger set the groups
G
and
G_{T}
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 >∈ D_{adbdh}
; otherwise it sets
' ,Z >∈ D_{rand}
.
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 ,α_{i} ,β_{i} ,γ_{i}
at random from
Z_{p}
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
O_{kg}
, the rekey generation oracle
O_{rkg}
, and the reencryption oracle
O_{ree}
.
A
makes several queries to the
O_{kg}
with an index set
I_{q}
. According to the security game, if
I_{q}
satisfies
AS
^{*}
, it outputs ┻.
Otherwise,
S
queries
from the oracle and outputs
usk
.
A
makes a query to
O_{rkg}
with an index set
I_{q}
and an access structure
AS
. According to the security game, if
I_{q}
satisfies
AS
^{*}
, it outputs ┻. Otherwise,
S
submits
I_{q}
to
O_{kg}
and obtains a secret key
.
S
executes the following procedure:
It selects a random
d ∈ Z_{p}
and set
For
i ∈ N D^{'}_{ i ,1} = D_{i ,1} ・h^{d}
, it outputs
, in which
C'
is the ciphertext of ℑ under the access structure
AS
'.
A
makes a query to
O_{ree}
with an index set
I_{q}
, an access structure
AS'
, and a ciphertext
According to the security game, if
I_{q}
satisfies
AS
^{*}
, it outputs ┻. If
I_{q}
does not satisfy
AS
, it outputs ┻. Then
S
submits (
I_{q}
,
AS'
) to the rekey generation oracle and obtains
.
S
uses
rk
to reencrypt the ciphertext
C
. For
i ∈ N
:
+d_{i}
appears in
AS
,
−d_{i}
appears in
AS
,
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 messages
M_{0}
and
M_{1}
in length.
S
produces a challenge ciphertext:
Phase 2: Same procedure as Phase 1.
Guess: A tuple was given from
D_{adbdh}
when
S
outputs
c' = 1
and
A
gives a correct guess
μ' = μ
;otherwise a tuple was given from
D_{rand}
when
S
outputs
c' = 0
.
According to
[3]
, the advantage of the simulator to output a correct
v ' = v
is
Theorem 2: If the CTDH assumption holds in
G , G_{T}
,then the ABPRE scheme has master key security.
Proof: The simulator
S
receives a tuple
and a challenge index set
I
* . To output
g^{abc}
, the simulator
S
does as follows:
Init:
S
chooses
α_{i} ,β_{i} ,γ_{i}
at random from
Z_{p}
for
i ∈ N
and generates the public key and set
Y = 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 parameter
Key generation oracle:
A
makes a query to the key generation oracle with an index set
I_{q} ⊆ N
where
I_{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
chooses
r'_{i} ∈ Z_{p}
at random and implicitly sets
r_{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
: if
i ∈ 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 set
I_{q}
⊆
N
and access structure
AS
, if
I_{q} ≠ I*
. , obtain
usk
from
KGEN
(
I_{q}
) and generate
rk
=
RKGEN
(
usk ,AS
) ; else
I_{q}
=
I
*.
Select
j ∈ I*
and
at 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 of
g_{d} · g^{t}
under the access structure
AS
.
Reencryption oracle:
A
makes a query to the key generation oracle with an index set
I_{q}
⊆
N
and access structure: if
I_{q}
≠
I *
. , obtain
rk
from
RKGEN (usk ,AS')
and generate
C' = REENC(rk ,C)
; else
I_{q}
=
I*
.
For
i ∈ N
:
 +
d_{i}
appears in
AS
,
where
Computational time of each algorithm
Computational time of each algorithm
 −
d_{i}
appears in
AS
,
where
 Otherwise,
where
It outputs a secret key
usk
^{*}
for
I
^{*}
including
If 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
and
kC_{e}
denote the ktimes calculation over group
G
and pairing, respectively. Let
u = {att_{1},att_{2},...,att_{n}}
be the set of attributes.
Some properties of attributebased encryption schemesDBDH: decisional bilinear DiffieHellman, CTDH: complex triple DiffieHellman, ADBDH: augment decisional bilinear DiffieHellman.
Some properties of attributebased encryption schemes DBDH: decisional bilinear DiffieHellman, CTDH: complex triple DiffieHellman, ADBDH: augment decisional bilinear DiffieHellman.
Let
r_{1}
and
r_{2}
be a set of attributes associated with the ciphert
ext 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).
Acknowledgements
This work was supported for two years by a Pusan National University Research grant.
Boneh D
,
Franklin M. K
2001
“Identitybased 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 identitybasedencryption”
Proceedings of the 26th Annual International Cryptology Conference on Advances in Cryptology
Santa Barbara: CA
290 
307
Sahai A
,
Waters B
2005
“Fuzzy identitybased 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
“Attributebased encryption for finegrained 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
“Ciphertextpolicy attributebased 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 reencryptionwith 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 attributebased 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
“Chosenciphertext secure proxyreencryption”
Proceedings of the 14th ACM Conference o nComputer and Communications Security
Alexandria: VA
185 
194
Nishide T
,
Yoneyama K
,
Ohta K
2008
“Attributebased encryption with partially hidden encryptorspecified access structures”
Proceedings of the 6th International Conference on Applied Cryptography and Network Security
New York: NY
111 
129
Waters B
2008
“Ciphertextpolicy attributebased 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