Attribute-based Proxy Re-encryption 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
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
-
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.
In ABPRE, a user can re-encrypt the ciphertext using a re-key. Detailed relationships are shown in Fig. 1. First
U1 generates the ciphertextC1 , which can be decrypted withU1 ’s attributes. One day,U1 is absent, but we need to read the data fromC1 . 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.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 keymk .KEYGEN (
S, mk ): The key generation algorithm takes as input the master keymk and a set of attributesS 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 and access structureusk . It outputs a re-keyAS 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 RE-ENC (
rk ,C ): The re-encryption algorithm takes as input the re-keyrk and a ciphertextC . First the algorithm checks the index set inrk . Ifrk satisfies the access structure ofC , it outputs a re-encrypted ciphertextC ' ; otherwise, it rejects the re-key.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 .In this section, some definitions which are the basis of attribute-based encryption schemes, including our scheme, are presented.
Definition 1. Bilinear groups and a bilinear map are defined as follows:G andGT are finite cyclic groups of prime orderp . e is an efficiently computable bilinear map or pairinge : G ×G →GT , with the following properties;Bilinearity: For any
g,h ∈ G , anda,b ∈ Zp , we havee(ga ,hb) = e(g,h)a·b .Non-degeneracy:
e(g,g) ≠ 1.Note that
e(*,*) is symmetric sincee(ga ,gb) = e(g,g)a·b = e(gb ,ga) .Definition 2. Complex Triple Diffie-Hellman (CTDH) problem. Lete : G ×G → GT be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersn,a,b,c,d ,R ∈ Zp . Given a tupleas inputs, output
gabc .Definition 3. Augment Diffie-Hellman (ADH) problem. Lete : G × G → GT be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersa,b ∈ Zp . Given a tupleas inputs, output
gab .Definition 4. The CTDH assumption holds inG if no probabilistic polynomial time adversary is able to outputgabc fromwith non-negligible advantage, where random numbers
n,a,b,c,d ,R ∈ Zp 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 outputsgRc from the CTDH oracle with inputsThe CTDH problem is the basis of the master key security in our scheme.
Definition 5. Augment decisional bilinear Diffie-Hellman (ADBDH) problem. Lete : G × G → GT be a bilinear map, whereG has prime orderp andg is a generator ofG , random numbersa,b,c ∈ Zp . 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 non-negligible advantage, where
a,b,c,z ∈ Zp and a generatorg ∈ G are chosen independently and uniformly at random.IV. ATTRIBUTE-BASED PROXY RE-ENCRYPTION WITH CONSTANT PAIRING OPERATION LATENCY
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 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 .
SETUP (1
k ) : A bilinear groupG of prime orderp ,with bilinear mape : G × G → GT is generated. Next, it selects elementsk ,y ,z ,ti (1≤i ≤ 3n ) inZp and two generatorsg,h ofG at random. LetY := e(g,h)y andTi := gti for each 1≤i ≤ 3n . The public parameterpp includesThe master key
mk is< k ,y ,z ,{ti}1≤ i ≤ 3n > .KGEN(
S,mk ) : LetS denote an index set of attributes. It chooses a randomr1,...,rn from theZp and setsr = r1 + r2 + ... + rn . It computesand for each
= {1,2,...,i ∈ N (Nn }) :(Di,1 = hri )i∈N . This outputs a user’s secret keyENC(
m, ) : LetAS denote an access structure. To encrypt a messageAS m ∈ GT , it selects a randoms ∈ Zp and computesFor
i ∈ N : if+di appears as ,AS Ci = Tsi ; if-di appears as ,AS Ci = Tsn+i ; otherwise,Ci = Ts2n+i . It outputsRKGEN(
) : Letusk ,AS ' denote a valid secret key consisting ofusk and let
denote an access structure. It selects a randomAS 'd ∈ Zp and setFor
i ∈ N D'i ,1 =Di ,1 ·hd ; C' is the ciphertext of ? under the access structure .AS 'It outputs
REENC(
rk ,C ) : Letrk denote a valid re-key consisting ofand
C denote a well-formed ciphertextThis step checks whether
S satisfies ; if not, output ┻ ; otherwise, forAS i ∈ N :+di appears inAS ,?di appears inAS ,Otherwise,
It computes
and
Next it computes
E = e(C,DT ) = e(g,h)(n·d+r)(k·s·z) It then computes
It outputs a re-encrypted ciphertext
Note that
Cre can be re-encrypted iteratively. Thus we would obtainwhere
C'' is obtained from the REENC algorithm with the input of anotherrk' andC' . The size of the ciphertext and re-encryption 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 well-formed ciphertext consisting of, for
i ∈ N :+di appears inAS ,?di appears inAS ,Otherwise,
It computes
and
Next it computes
E = e(C,DT ) = e(g,h)k·r·s·z It outputs
Otherwise, if
C is a re-encrypted well-formed ciphertext consisting of, then it decrypts
C' usingusk and obtains ? =gd . Then it outputsOtherwise, if is a multi-time re-encrypted well-formed ciphertext, then decryption is similar with the above phases.
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 distinguishDadbdh fromDrand with the non-negligible advantageWe first suppose the challenger set the groups
G andGT 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 >∈ Dadbdh ; otherwise it sets .' ,Z >∈ Drand 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 fromZp 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 oracleOkg , the re-key generation oracleOrkg , and the re-encryption oracleOree .A makes several queries to theOkg with an index setIq . According to the security game, ifIq satisfies * , it outputs ┻.AS Otherwise,
S queriesfrom the oracle and outputs
usk .A makes a query toOrkg with an index setIq and an access structureAS . According to the security game, ifIq satisfiesAS * , it outputs ┻. Otherwise,S submitsIq toOkg and obtains a secret key.
S executes the following procedure:It selects a random
d ∈ Zp and setFor
i ∈ N D' i ,1 = Di ,1 ·hd , it outputs, in which
C' is the ciphertext of ? under the access structureAS '.A makes a query toOree with an index setIq , an access structureAS' , and a ciphertextAccording to the security game, if
Iq satisfiesAS * , it outputs ┻. IfIq does not satisfyAS , it outputs ┻. ThenS submits (Iq ,AS' ) to the re-key generation oracle and obtains.
S usesrk to re-encrypt the ciphertextC . Fori ∈ N :+di appears inAS ,?di appears inAS ,Otherwise,
.It computes
, and
Next it computes
E = e(C,DT ) = e(g,h)(n·d+r)(k·s·z) Finally, it computes
It outputs a re-encrypted ciphertext
Challenge:
A submits two equal messagesM0 andM1 in length.S produces a challenge ciphertext:Phase 2: Same procedure as Phase 1.
Guess: A tuple was given from
Dadbdh whenS outputsc' = 1 andA gives a correct guessμ' = μ ;otherwise a tuple was given fromDrand 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 , GT ,then the ABPRE scheme has master key security.Proof: The simulator
S receives a tupleand a challenge index set
I * . To outputgabc , the simulatorS does as follows:Init:
S choosesαi ,βi ,γi at random fromZp fori ∈ N and generates the public key and setY = 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 parameterKey generation oracle:
A makes a query to the key generation oracle with an index setIq ⊆ N whereIq ≠ 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 choosesr'i ∈ Zp at random and implicitly setsri in the following ways:ri =br'i (i ≠ j ; ),rj =ab + br'i (otherwise).Denote
and
For
i ∈ Iq , i ≠ j : ifi ∈ I* else
i ? I* For
i ? Iq , 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 setIq ⊆N and access structureAS , ifIq ≠ I* . , obtainusk fromKGEN (Iq ) and generaterk =RKGEN (usk ,AS ) ; elseIq =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 ofgd · gt under the access structureAS .Re-encryption oracle:
A makes a query to the key generation oracle with an index setIq ⊆N and access structure: ifIq ≠I * . , obtainrk fromRKGEN (usk ,AS') and generateC' = REENC(rk ,C) ; elseIq =I* .-For
i ∈ N :- +
di appears inAS ,where
- ?
di 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 re-key could be correctly generated from the Key generation and Rekey generation oracle.
It outputs
and solves the CTDH problem.
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 andkCe denote the k-times calculation over groupG and pairing, respectively. Letu = {att1,att2,...,attn} be the set of attributes.Let
r1 andr2 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 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.
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).
-
[Fig 1.] The attribute-based proxy re-encryption scheme system.
-
[Table 1.] Computational time of each algorithm
-
[Table 2.] Some properties of attribute-based encryption schemes