# Time-and-ID-Based Proxy Reencryption Scheme

Authors: Kambombo Mtonga; Anand Paul; Seungmin Rho
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Time- and ID-based proxy reencryption scheme is proposed in this paper in which a type-based proxy reencryption enables the delegator to implement fine-grained policies with one key pair without any additional trust on the proxy. However, in some applications, the time within which the data was sampled or collected is very critical. In such applications, for example, healthcare and criminal investigations, the delegatee may be interested in only some of the messages with some types sampled within some time bound instead of the entire subset. Hence, in order to carter for such situations, in this paper, we propose a time-and-identity-based proxy reencryption scheme that takes into account the time within which the data was collected as a factor to consider when categorizing data in addition to its type. Our scheme is based on Boneh and Boyen identity-based scheme (BB-IBE) and Matsuo’s proxy reencryption scheme for identity-based encryption (IBE to IBE). We prove that our scheme is semantically secure in the standard model.


---

## Body

## 1. Introduction

A proxy reencryption (PRE) scheme involves three parties: delegator (Alice), delegatee (Bob), and a proxy (semitrusted third party). Alice assigns a key to a proxy to reencrypt all her messages encrypted with her public key such that the reencrypted ciphertexts can be decrypted with Bob’s private key. Due to this delegation of decrypting capability, various applications of PRE have been suggested, for example, email forwarding, digital rights management (DRM), law enforcement, and secure network file storage [1–4]. Charlie provides multiple-hop or multiuse proxy to the systems while PRE schemes could be defined based on the direction of operation, number of hops (possible reencryption), and their structure.Unidirectional PRE implies that the proxy can reencrypt a message from Alice to Bob but cannot reencrypt a message from Bob to Alice using the same key, whilebidirectional PRE applies from sender to recipient and vice versa. PRE schemes capable of reencrypting a message from Alice to Bob and then from Bob to Charlie are said to be a multihop or multi-use proxy [5, 6]. On the other hand, single-hop schemes use a specific key to reencrypt between only two entities. It is important that the PRE scheme should at least satisfy the following requirements: (1) a proxy alone cannot obtain the underlying plaintext and (2) delegatee cannot obtain the underlying plaintext without the proxy’s cooperation.Based on a simple modification of the ElGamal encryption scheme, Blaze et al. [7] in 1998 proposed the first PRE scheme where the proxy is kept from knowing plaintexts and secret keys [8]. Ateniese et al. [1] proposed a number of unidirectional PRE schemes and discussed their several potential applications such as distributed secure file systems. Later, many unidirectional PRE schemes with different properties have been proposed [9–11]. In recent past, the concept of identity-based proxy reencryption (IB-PRE) has gained popularity among researchers [12, 13]. It (IBE) was first introduced by Shamir [14]. The main idea of ID-based cryptosystems is that the identity information of each user (such as E-mail addresses, security number, or IP addresses) works as his/her public key. In other words, the user’s public key can be calculated directly from his/her identity rather than being extracted from a certificate issued by a certificate authority (CA) as is the case in certificate-based cryptosystems. ID-based public key setting serves as a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. After Boneh and Franklin [15] proposed a practical IBE scheme, Green and Ateniese later [16] proposed the first IB-PRE scheme. IB-PRE is IBE which permits delegation of decryption capability. They also discussed its several interesting applications such as bridging IBE and public key encryption (PKE). Since then, several IB-PRE schemes have been proposed [17, 18]. In IB-PRE, a user who has a secret key corresponding to his/her public identity can decrypt a ciphertext encrypted with his/her identity as in IBE. In 2007, Matsuo proposed the concept of four types of PRE schemes: certificate-based PKE (CBE) to CBE, IBE to CBE, CBE to IBE, and IBE to IBE [19]. Matsuo’s schemes are based on ElGamal-type CBE scheme and BB-IBE [20]. Now CBE to IBE and IBE to IBE PRE schemes are being standardized by IEEEP1363.3 working group [21].In 2008, Tang [22] first introduced the concept of type-based PRE (TB-PRE). He proposed two schemes; one scheme achieved ciphertext privacy and was proved chosen plaintext attack (IND-PR-CPA) secure under the eXternalDiffie-Hellman (XDH) and co-BDH assumptions, while the other scheme achieved chosen ciphertext attack (IND-PR-CCA) security under the knowledge of exponent (KE) and the bilinear Diffie-Hellman (BDH) assumptions. In a TB-PRE scheme, the delegator categorizes his/her messages (ciphertexts) into different subsets and is capable of delegating the decryption right of each subset to a specific delegatee. The ciphertexts for the delegator are generated based on the delegator’s public key and the message type which is used to identify the message subset. TB-PRE as a variant of PRE could be considered as a subset of conditional proxy reencryption (C-PRE). In C-PRE schemes, ciphertexts are generated with respect to a certain condition and the proxy can translate a ciphertext only if the associated condition is satisfied [23, 24]. Ibraimi et al. [25] proposed the first type-and-identity-based proxy reencryption (TIB-PRE) scheme based on the Boneh-Franklin IBE scheme. Their scheme was proved semantically secure against an adaptive chosen plaintext attack for the delegator (IND-ID-DR-CPA). They further showed how their scheme could be used by a patient to enforce his/her personal health record (PHR) disclosure policies. A TIB-PRE scheme is basically a TB-PRE scheme that encompasses IBE and PRE.


### 1.1. Motivation and Contribution

As pointed out in [22, 25], the existing PRE schemes have a limitation in that the proxy could reencrypt all ciphertexts encrypted under delegator’s public key and pass them to the delegatee. In order to implement fine-grained access control policies, the delegator (1) can choose a different key pair for each possible subset of his/her messages and choose a proxy to delegate his decryption right or (2) can choose to trust the proxy to enforce his policies by reencrypting the predefined subset of his ciphertexts to the specific delegatee. However, both of these approaches are infeasible in practice because they are too involving for the delegator and also demand strong trust on the proxy. On the other hand, in a type-based proxy reencryption scheme, the delegator can categorize his messages (ciphertexts) into different subsets and is capable of delegating the decryption right of each subset to a specific delegatee. Hence, type-based proxy reencryption enables the delegator to implement fine-grained policies with one key pair and without any additional trust on the proxy.Despite this advantage, however, in some applications, instead of delegating all the messages under a type-based subset, the delegator may be required to delegate just some of the messages within the subset. This may be because the delegate could be interested in specific messages collected or sampled within a specified period of time. For example, (1) in healthcare, a physician maybe interested only in a patient’s recent (e.g., last five months) prescription history to check if his/her recent drug interactions could conflict with the proposed course of treatment. (2) In criminal investigations, an investigator may only be interested in video footage from closed circuit television recordings (CCTV) of the crime scene that were taken within the time bound of the occurrence of the crime. In view of such cases, we argue that incorporating an element of time period (e.g., hours, days, etc.) in TBE would give the delegator more flexibility to provide the proxy with more fine-grained reencryption capabilities. Hence, in this paper we propose a time-and-identity-based proxy reencryption scheme (tm-IB-PRE) to solve aforementioned shortfalls in PRE schemes while at the same time adopting the advantages of TB-PRE and IBE schemes. Our scheme is based on BB-IBE and Matsuo’s IBE to IBE PRE schemes. Unlike the existing TB-PRE schemes, the ciphertexts for the delegator in our scheme are generated based on the delegator’s public key and some specified time periods. We find this assumption plausible because it is common practice to attach date and even time to data upon its collection. Note that our scheme can be considered as a special case of TBE. As such we assume that the delegator will first categorize his/her messages into subsets according to type and then, as may be requested by the delegatee, the delegator can further recategorizes the messages into refined subsets depending on specified time period. The reencryption key in our scheme is independent of the delegatee’s private key. As a result, our scheme can achieve master secret security.


## 1.1. Motivation and Contribution

As pointed out in [22, 25], the existing PRE schemes have a limitation in that the proxy could reencrypt all ciphertexts encrypted under delegator’s public key and pass them to the delegatee. In order to implement fine-grained access control policies, the delegator (1) can choose a different key pair for each possible subset of his/her messages and choose a proxy to delegate his decryption right or (2) can choose to trust the proxy to enforce his policies by reencrypting the predefined subset of his ciphertexts to the specific delegatee. However, both of these approaches are infeasible in practice because they are too involving for the delegator and also demand strong trust on the proxy. On the other hand, in a type-based proxy reencryption scheme, the delegator can categorize his messages (ciphertexts) into different subsets and is capable of delegating the decryption right of each subset to a specific delegatee. Hence, type-based proxy reencryption enables the delegator to implement fine-grained policies with one key pair and without any additional trust on the proxy.Despite this advantage, however, in some applications, instead of delegating all the messages under a type-based subset, the delegator may be required to delegate just some of the messages within the subset. This may be because the delegate could be interested in specific messages collected or sampled within a specified period of time. For example, (1) in healthcare, a physician maybe interested only in a patient’s recent (e.g., last five months) prescription history to check if his/her recent drug interactions could conflict with the proposed course of treatment. (2) In criminal investigations, an investigator may only be interested in video footage from closed circuit television recordings (CCTV) of the crime scene that were taken within the time bound of the occurrence of the crime. In view of such cases, we argue that incorporating an element of time period (e.g., hours, days, etc.) in TBE would give the delegator more flexibility to provide the proxy with more fine-grained reencryption capabilities. Hence, in this paper we propose a time-and-identity-based proxy reencryption scheme (tm-IB-PRE) to solve aforementioned shortfalls in PRE schemes while at the same time adopting the advantages of TB-PRE and IBE schemes. Our scheme is based on BB-IBE and Matsuo’s IBE to IBE PRE schemes. Unlike the existing TB-PRE schemes, the ciphertexts for the delegator in our scheme are generated based on the delegator’s public key and some specified time periods. We find this assumption plausible because it is common practice to attach date and even time to data upon its collection. Note that our scheme can be considered as a special case of TBE. As such we assume that the delegator will first categorize his/her messages into subsets according to type and then, as may be requested by the delegatee, the delegator can further recategorizes the messages into refined subsets depending on specified time period. The reencryption key in our scheme is independent of the delegatee’s private key. As a result, our scheme can achieve master secret security.


## 2. Preliminaries

In this section, we first review the basic concept of the bilinear maps and related assumptions. Then, a brief discussion of IBE and TIB-PRE together with their respective security models will follow [26].Definition 1.
LetG and G1 be two cyclic multiplicative groups with prime order p. Let g be a generator of G and let e^: G×G→G1 be a bilinear map with the following properties.(i)
Bilinearity: for all u,v∈G and for all a,b∈Z, we have e^(ua,vb)=e^(u,v)ab.(ii)
Nondegeneracy: the map does not send all pairs in G×G to the identity in G1. Observe that since G and G1 are groups of prime order this implies that if g is a generator of G, then e^(g,g) is a generator of G1. G is said to be a bilinear group if the group operation in G and the bilinear map e^: G×G→G1 are both efficiently computable.
We assume that there is an efficient algorithmGen for generating bilinear groups. The algorithmGen takes a security parameter k as input and outputs a tuple (p, G, G1, g, and e^).Definition 2.
The decisional bilinear Diffie-Hellman (dBDH) problem in groups(G,G1) is as follows. Given (g,ga,gb,gc,X)∈G×G1 with unknown a,b,c∈RZp*, decide whether X=e^(g,g)abc. The advantage of an algorithm A in solving the dBDH problem is defined as follows:
(1)AdvGdBDH(A)=|Pr[A(g,ga,gb,gc,e^(g,g)abc)=0]e-Pr⁡[A(g,ga,gb,gc,X)=0]|,
where the probability is over the random choice of generator g∈RG, the randomly chosen integers a,b,c∈RZp*, the random choice of X∈RG1, and the random bits used by A. We say that the (k,t,ε-) dBDH assumption holds in G if no t-time algorithm has advantage at least ε in solving the dBDH problem in G under a security parameter k.


### 2.1. Definition and Security Notion for IBE

Definition 3.
An IBE scheme consists of four algorithms:SetupIBE, KeyGenIBE, EncryptIBE, and DecryptIBE [27].
S
e
t
u
p
I
B
E
(
1
k
)
. This algorithm takes a security parameter k as input and outputs parametersparams which are distributed to users and the master key mk which is kept private.
K
e
y
G
e
n
I
B
E
(
p
a
r
a
m
s
,
m
k
,
i
d
)
. This algorithm takes parametersparams, the master key mk, and an identifier id as input and it outputs a private key did associated with id.
E
n
c
r
y
p
t
I
B
E
(
p
a
r
a
m
s
,
M
,
i
d
)
. This algorithm takes parametersparams, a message M, and an identifier id as input and outputs a ciphertext Cid encrypted under id.
D
e
c
r
y
p
t
I
B
E
(
C
i
d
,
d
i
d
)
. This algorithm takes a ciphertext Cid associated with an identifier id as input and outputs a message M or ⊥ as an error message.Definition 4.
The selective identity chosen plaintext (IND-sID-CPA) security for an IBE scheme is defined as a game between an adversaryA and a challenger C, where the challenger simulates the protocol execution and answers queries from the adversary.
Initialization. The adversary outputs an identifier id* where it wishes to be challenged.
S
e
t
u
p
I
B
E
. The challenger runs the setup algorithm and returns parametersparams to the adversary while keeping the master key mk to itself.
Phase 1. The adversary adaptively issues q1⋯qm private key queries for idi≠id*. The challenger runs the algorithm KeyGenIBE and outputs the private keys didi corresponding to idi. The challenger sends didi to the adversary.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. Given (M0,M1,id*), the challenger picks a random bit b∈R{0,1} and sends the challenge ciphertext C* = EncryptIBE(params,Mb,id*) to the adversary.
Phase 2. The adversary continues to issue qm+1⋯qn queries as in phase 1 but with restriction that he/she cannot issue private key queries for idi = id*. The challenger responds as in phase 1.
Guess. Finally, the adversary issues a guess b′∈R{0,1}. The adversary wins the game if b′=b.
An IBE scheme is IND-sID-CPA secure if|Pr⁡[b′=b]-1/2| is negligible.Definition 5.
We define the advantage of adversaries in an IND-sID-CPA games as(2)AdvAgame=(Pr[b′=b]-12).
An IBE system is said to be (k,t,q,ε-) IND-sID-CPA secure if for any t-time IND-sID-CPA adversary A that makes at most q chosen secret key queries under a security parameter k we have AdvAgame<ε. As shorthand, we say that an IBE system is (k,t,q,ε-) IND-sID-CPA secure.


### 2.2. Definition and Security Notion for TIBE and TIB-PRE Scheme

Definition 6.
We base our definitions on [22, 25]. A TIBE scheme consists of four algorithms: SetupTIBE, KeyGenTIBE, EncryptTIBE, and DecryptTIBE. Both SetupTIBE and KeyGenTIBE are run under IBE. Below, we define EncryptTIBE and DecryptTIBE. Note that we adopt the notation T to stand for message type.
E
n
c
r
y
p
t
T
I
B
E
(
p
a
r
a
m
s
,
M
,
i
d
,
T
)
. This algorithm takes parametersparams, a message M, an identifier id, and a message type T as input and it outputs a ciphertext Cid encrypted under id. Both Cid and T are sent to the receiver.
D
e
c
r
y
p
t
T
I
B
E
(
C
i
d
,
d
i
d
,
T
)
. This algorithm takes the ciphertext Cid, the private key did, and a message type T as input. The algorithm outputs a message M of type T.Definition 7.
A TIB-PRE scheme is a PRE that combines the concepts of both IBE and type-based encryption. The scheme consists of six algorithms:SetupTIB-PRE, KeyGenTIB-PRE, PextractTIB-PRE, EncryptTIB-PRE, PreencTIB-PRE, and DecryptTIB-PRE. SetupTIB-PRE, KeyGenTIB-PRE, EncryptTIB-PRE, and DecryptTIB-PRE are defined as above. Below we define PextractTIB-PRE and PreencTIB-PRE.
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
(
d
i
d
i
d
,
i
d
′
,
T
)
. This algorithm is run by the delegator. It takes a delegator’s private key did, the delegator’s identifier id, the delegatee’s identifier id′, and a message type T as input. The algorithm outputs rkid→id′ as the reencryption key.
P
r
e
e
n
c
T
I
B
-
P
R
E
(
C
i
d
,
r
k
i
d
→
i
d
′
,
T
)
. This algorithm is run by the proxy. It takes the ciphertext Cid associated with delegator’s identifier, the reencryption key rkid→id′, and a message type T as input. The algorithm outputs a new ciphertext C′ for delegatee.Definition 8.
We model selective identity chosen plaintext security for a TIB-PRE scheme as a game between an adversaryA and a challenger C, where the challenger simulates the protocol execution and answers queries from the adversary.
Initialization. The adversary outputs an identity id* and T* where it wishes to be challenged.
S
e
t
u
p
T
I
B
-
P
R
E
. The challenger runs the setup algorithm and returns parametersparams to the adversary while keeping the master key mk to itself.
Phase 1. Taking parametersparams as input, the adversary adaptively issues the following queries.
P
r
i
v
a
t
e
K
e
y
q
u
e
r
y
T
I
B
-
P
R
E
. The adversary queries with any identifier idi≠id*. The challenger outputs private keys didi corresponding to idi. The challenger sends didi to adversary.
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
. The adversary queries with (idi, id′, T). If id′ has been queried to a private key query, then the challenger halts. Otherwise, the challenger outputs a reencryption key rkid→id′ for type T and sends it to the adversary.
P
r
e
e
n
c
T
I
B
-
P
R
E
. The adversary queries the challenger with (M, id, id′, T). The challenger first computes Cid=EncryptTIB-PRE(M, id, T) and returns C′ = PreencTIB-PRE(Cid, rkid→id′, T) to the adversary which is obtained by applying the delegation key rkid→id′ to Cid.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. The challenger picks a random bit b∈R{0,1} and sets the challenge ciphertext to C* = EncryptTIB-PRE(params, Mb, id*, T*). It sends C* as the challenge to the adversary.
Phase 2. The adversary continues to issue queries as in phase 1 but with restrictions that(i)
he/she cannot issue private key queries foridi=id*;(ii)
if there is aPreencTIB-PRE query with (M, id, id*, T), then (id, id*, T) has not been queried to PextractTIB-PRE.The challenger responds as in phase 1.
Guess. Finally, the adversary outputs a guess b′∈R{0,1}. The adversary wins if b = b′.
At the end of the game, the adversary’s advantage is defined to beAdvAgame=(Pr[b′=b]-1/2).


## 2.1. Definition and Security Notion for IBE

Definition 3.
An IBE scheme consists of four algorithms:SetupIBE, KeyGenIBE, EncryptIBE, and DecryptIBE [27].
S
e
t
u
p
I
B
E
(
1
k
)
. This algorithm takes a security parameter k as input and outputs parametersparams which are distributed to users and the master key mk which is kept private.
K
e
y
G
e
n
I
B
E
(
p
a
r
a
m
s
,
m
k
,
i
d
)
. This algorithm takes parametersparams, the master key mk, and an identifier id as input and it outputs a private key did associated with id.
E
n
c
r
y
p
t
I
B
E
(
p
a
r
a
m
s
,
M
,
i
d
)
. This algorithm takes parametersparams, a message M, and an identifier id as input and outputs a ciphertext Cid encrypted under id.
D
e
c
r
y
p
t
I
B
E
(
C
i
d
,
d
i
d
)
. This algorithm takes a ciphertext Cid associated with an identifier id as input and outputs a message M or ⊥ as an error message.Definition 4.
The selective identity chosen plaintext (IND-sID-CPA) security for an IBE scheme is defined as a game between an adversaryA and a challenger C, where the challenger simulates the protocol execution and answers queries from the adversary.
Initialization. The adversary outputs an identifier id* where it wishes to be challenged.
S
e
t
u
p
I
B
E
. The challenger runs the setup algorithm and returns parametersparams to the adversary while keeping the master key mk to itself.
Phase 1. The adversary adaptively issues q1⋯qm private key queries for idi≠id*. The challenger runs the algorithm KeyGenIBE and outputs the private keys didi corresponding to idi. The challenger sends didi to the adversary.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. Given (M0,M1,id*), the challenger picks a random bit b∈R{0,1} and sends the challenge ciphertext C* = EncryptIBE(params,Mb,id*) to the adversary.
Phase 2. The adversary continues to issue qm+1⋯qn queries as in phase 1 but with restriction that he/she cannot issue private key queries for idi = id*. The challenger responds as in phase 1.
Guess. Finally, the adversary issues a guess b′∈R{0,1}. The adversary wins the game if b′=b.
An IBE scheme is IND-sID-CPA secure if|Pr⁡[b′=b]-1/2| is negligible.Definition 5.
We define the advantage of adversaries in an IND-sID-CPA games as(2)AdvAgame=(Pr[b′=b]-12).
An IBE system is said to be (k,t,q,ε-) IND-sID-CPA secure if for any t-time IND-sID-CPA adversary A that makes at most q chosen secret key queries under a security parameter k we have AdvAgame<ε. As shorthand, we say that an IBE system is (k,t,q,ε-) IND-sID-CPA secure.


## 2.2. Definition and Security Notion for TIBE and TIB-PRE Scheme

Definition 6.
We base our definitions on [22, 25]. A TIBE scheme consists of four algorithms: SetupTIBE, KeyGenTIBE, EncryptTIBE, and DecryptTIBE. Both SetupTIBE and KeyGenTIBE are run under IBE. Below, we define EncryptTIBE and DecryptTIBE. Note that we adopt the notation T to stand for message type.
E
n
c
r
y
p
t
T
I
B
E
(
p
a
r
a
m
s
,
M
,
i
d
,
T
)
. This algorithm takes parametersparams, a message M, an identifier id, and a message type T as input and it outputs a ciphertext Cid encrypted under id. Both Cid and T are sent to the receiver.
D
e
c
r
y
p
t
T
I
B
E
(
C
i
d
,
d
i
d
,
T
)
. This algorithm takes the ciphertext Cid, the private key did, and a message type T as input. The algorithm outputs a message M of type T.Definition 7.
A TIB-PRE scheme is a PRE that combines the concepts of both IBE and type-based encryption. The scheme consists of six algorithms:SetupTIB-PRE, KeyGenTIB-PRE, PextractTIB-PRE, EncryptTIB-PRE, PreencTIB-PRE, and DecryptTIB-PRE. SetupTIB-PRE, KeyGenTIB-PRE, EncryptTIB-PRE, and DecryptTIB-PRE are defined as above. Below we define PextractTIB-PRE and PreencTIB-PRE.
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
(
d
i
d
i
d
,
i
d
′
,
T
)
. This algorithm is run by the delegator. It takes a delegator’s private key did, the delegator’s identifier id, the delegatee’s identifier id′, and a message type T as input. The algorithm outputs rkid→id′ as the reencryption key.
P
r
e
e
n
c
T
I
B
-
P
R
E
(
C
i
d
,
r
k
i
d
→
i
d
′
,
T
)
. This algorithm is run by the proxy. It takes the ciphertext Cid associated with delegator’s identifier, the reencryption key rkid→id′, and a message type T as input. The algorithm outputs a new ciphertext C′ for delegatee.Definition 8.
We model selective identity chosen plaintext security for a TIB-PRE scheme as a game between an adversaryA and a challenger C, where the challenger simulates the protocol execution and answers queries from the adversary.
Initialization. The adversary outputs an identity id* and T* where it wishes to be challenged.
S
e
t
u
p
T
I
B
-
P
R
E
. The challenger runs the setup algorithm and returns parametersparams to the adversary while keeping the master key mk to itself.
Phase 1. Taking parametersparams as input, the adversary adaptively issues the following queries.
P
r
i
v
a
t
e
K
e
y
q
u
e
r
y
T
I
B
-
P
R
E
. The adversary queries with any identifier idi≠id*. The challenger outputs private keys didi corresponding to idi. The challenger sends didi to adversary.
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
. The adversary queries with (idi, id′, T). If id′ has been queried to a private key query, then the challenger halts. Otherwise, the challenger outputs a reencryption key rkid→id′ for type T and sends it to the adversary.
P
r
e
e
n
c
T
I
B
-
P
R
E
. The adversary queries the challenger with (M, id, id′, T). The challenger first computes Cid=EncryptTIB-PRE(M, id, T) and returns C′ = PreencTIB-PRE(Cid, rkid→id′, T) to the adversary which is obtained by applying the delegation key rkid→id′ to Cid.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. The challenger picks a random bit b∈R{0,1} and sets the challenge ciphertext to C* = EncryptTIB-PRE(params, Mb, id*, T*). It sends C* as the challenge to the adversary.
Phase 2. The adversary continues to issue queries as in phase 1 but with restrictions that(i)
he/she cannot issue private key queries foridi=id*;(ii)
if there is aPreencTIB-PRE query with (M, id, id*, T), then (id, id*, T) has not been queried to PextractTIB-PRE.The challenger responds as in phase 1.
Guess. Finally, the adversary outputs a guess b′∈R{0,1}. The adversary wins if b = b′.
At the end of the game, the adversary’s advantage is defined to beAdvAgame=(Pr[b′=b]-1/2).


## 3. Our Construction

In this section, we propose our time-and-identity-based proxy reencryption scheme (tm-IB-PRE) based on BB-IBE and Matsuo ID-PRE scheme. We adopt the basic principles of TIB-PRE. First we describe our tm-IBE scheme followed by a discussion of the delegation process. In our scheme, we assume one level delegation, meaning that the delegatees will not further delegate their decryption rights to other users. We adopt tm to denote some specified period of time (date, month, or year). Our scheme consists of six algorithms, namely,Setup,KeyGen,Pextract,Encrypt,Preenc, andDecryp.S
e
t
u
p
(
1
k
)
. This algorithm is run by the PKG and works as follows: it takes the security parameter k and selects a random generator g∈G and random element g2∈RG. Pick a random α∈RZp* and set g1 = gα, mk = g2α, andparams = (g,g1, g2). Here, mk = α is the master secret key andparams are public parameters.K
e
y
G
e
n
(
p
a
r
a
m
s
,
m
k
,
i
d
)
. Here, the PKG takes parametersparams, master key mk = α, and an identifier id as input. The PKG picks a random value x∈RZp* and outputs a private key did corresponding to id, where
(3)did=(y0,y1)=(g2α(g1id)x,gx).E
n
c
r
y
p
t
(
p
a
r
a
m
s
,
M
,
i
d
,
t
m
)
. To encrypt a message M bounded by time tm, the message sender picks r∈RZp* at random, computes Y = e^(g1,g2), and outputs ciphertext Cid, where
(4)Cid=(c1,c2,c3,c4)=(gr,(g1id)rtm,MYrtm,tm).Note thatY=e^(g1,g2) can be precomputed once and for all so that encryption does not require any pairing computations.D
e
c
r
y
p
t
(
C
i
d
,
d
i
d
,
t
m
)
. On inputting a ciphertext Cid=(c1,c2,c3,c4), a private key did=(y0,y1), and tm, the algorithm outputs M as follows:
(5)M=c3e^(y1,c2)e^(y0,(c1)c4)=Me^(g1,g2)rtm·e^(gx,g1idrtm)e^(g2α(g1id)x,grtm)=Me^(g,g2)αrtm·e^(g,g1)idrxtme^(g2,g)αrtm·e^(g1,g)idrxtm=M.


### 3.1. Delegation Process

To delegate his decryption right for some message subsets, the delegator makes use of the following algorithms.P
e
x
t
r
a
c
t
(
d
i
d
,
i
d
,
i
d
′
,
t
m
)
. This algorithm is run by the delegator. It takes private key of delegator did=(y0,y1), an identifier of delegator id and that of delegate id′, and sometime period tm as input. The algorithm outputs a reencryption key rkid→id′=(s0,s1,s2)=(y0v,y1,B), where v=(id∥l∥id′∣∣tm) and B=Encrypt(params,v,id′,tm), l∈RZp*.P
r
e
e
n
c
(
C
i
d
,
r
k
i
d
→
i
d
′
)
. This algorithm is run by the proxy. It takes a reencryption key rkid→id′=(s0,s1,s2) and a ciphertext Cid=(c1,c2,c3,c4), where tm=c4. The algorithm outputs a new ciphertext C′=(w1,w2,w3,w4), where
(6)w1=c3e^(s1,c2)e^(s0,(c1)c4),w2=c1,w3=c4,w4=s2.
Once delegatee receives the reencrypted ciphertext, he/she can obtain the plaintext by computing
(7)M=w1e^((w2)w3,Decrypt(w4,did′))-1=c3(e^(s1,c2)/e^(y0v,(c1)c4))e^((c1)c4,Decrypt(s2,did′))-1=c3(e^(s1,c2)/e^(y0,(c1)c4)·e^(v,(c1)c4))e^((c1)c4,Decrypt(s2,did′))-1=(Me^(g1,g2)rtme^(gx,g1idrtm)e^(g2α(g1idx),grtm)·e^(v,grtm))×(e^(grtm,v)-1)-1=(Me^(g,g2)αrtm·e^(g,g1)idxrtme^(g2,g)αrtm·e^(g1,g)idxrtm·e^(v,grtm))×(e^(grtm,v)-1)-1=M/e^(v,grtm)e^(v,grtm)-1=M.


### 3.2. Security Analysis

Theorem 9.
Suppose that the(k,t,ε-) dBDH assumption holds in G. Then, the proposed tm-IB-PRE scheme is (k,t′,q,ε′) selective identity (IND-sID-CPA) secure for any q, k, ε′≤ε and t′=t-Θ(τq), where τ is maximum time for an exponentiation in G.Proof.
LetA be an adversary against the proposed tm-IB-PRE scheme in the IND-sID-CPA sense. We construct an adversary B which solves the dBDH problem in G by utilizing A. Algorithm B is given (g,J1,J2,J3,U)=(g,ga,gb,gc,U) as input, where U=e^(g,g)abc or U=X∈RG1 and a,b,c∈RZp*. Algorithm B works by interacting with A in a selective identity game as follows.
Initialization. The selective identity game begins with A outputting a target identity id* and some fixed tm*.
Setup. To generate system parameters, algorithm B(i)
picksβ∈RZp*;(ii)
setsg1=J1 and g2=J2 and gives parameters params=(g,g1,g2) to A. The corresponding master key unknown to B is g2a=gab.
Phase 1. Taking parametersparams as input, the adversary adaptively issues the following queries.
Private Keyqueries.
A queries with any identifier idi≠id*. B outputs private keys didi corresponding to idi and sends it to A. Here,
(8)didi=(y0,y1)=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,g2-1/(idi-id*)gri(g2(-β)/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,),whereri∈RZp*.
Let x=ri-(b/(id-id*)); then didi is valid private key for idi. This is because
(9)didi=(y0,y1)=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,g2-1/(idi-id*)gri(g2(-β)/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,),whereri∈RZp*=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri(g1idi)b/(idi-id*),gri-(b/(idi-id*))g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri(g1idi)(b)/(idi-id*))=(g2a(g1id)ri(g1-id*gβ)ri(g1-id*gβ)-ri(g1idi)b/(idi-id*),gri-(b/(idi-id*))g2a(g1id)ri(g1-id*gβ)ri(g1-id*gβ)-ri(g1idi)(b)/(idi-id*))=(g2a(g1id)ri(g1idi)b/(idi-id*),gri-(b/(idi-id*)))=(g2a(g1id)ri-(b/(idi-id*)),gri-(b/(idi-id*)))=(g2a(g1id)x,gx).
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
.
A queries with (id,id′,tm). If id≠id* (in this case, id′ can be any identity), the simulator B first simulates KeyGen(params,mk,id) as above and gets did. Then, it runs Pextract(params,did,id′,tm) and returns the resulting reencryption key rkid→id′ to the adversary. Otherwise, if id=id*, B rejects the query.
Preenc.
A queries the challenger with (M,id,id′,tm′). B only faithfully responds to this query if id≠id* and tm′≠tm*. Otherwise, B halts.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. The challenger picks a random bit b∈R{0,1} and sets the challenge ciphertext to C*=(c1*,c2*,c3*,c4*)=(₭1,(₭2β)c4*, MbUc4*, c4*), where c4*=tm*. B returns C* to the adversary. Note that if U=e^(g,g)abc=e^(g1,g2)c, then C* is valid encryption of Mb. Otherwise, if U is uniform and independent in G1, then Mb is also independent of b in the adversary’s view.
Phase 2. The adversary issue further queries A and B responds as in phase 1.
Guess. Finally, A outputs a guess b′∈R{0,1}. Algorithm B concludes its own game by outputting a guess as follows. If b=b′, then B outputs 1 meaning U=e^(g,g)abc. Otherwise, it outputs 0 meaning U≠e^(g,g)abc.
B can perfectly simulate the reencryption key for id since it looks random and independent of any other values if A does not obtain the corresponding private key for id. When U=e^(g,g)abc, then A’s advantage is the same as B’s advantage for solving dBDH problem.


## 3.1. Delegation Process

To delegate his decryption right for some message subsets, the delegator makes use of the following algorithms.P
e
x
t
r
a
c
t
(
d
i
d
,
i
d
,
i
d
′
,
t
m
)
. This algorithm is run by the delegator. It takes private key of delegator did=(y0,y1), an identifier of delegator id and that of delegate id′, and sometime period tm as input. The algorithm outputs a reencryption key rkid→id′=(s0,s1,s2)=(y0v,y1,B), where v=(id∥l∥id′∣∣tm) and B=Encrypt(params,v,id′,tm), l∈RZp*.P
r
e
e
n
c
(
C
i
d
,
r
k
i
d
→
i
d
′
)
. This algorithm is run by the proxy. It takes a reencryption key rkid→id′=(s0,s1,s2) and a ciphertext Cid=(c1,c2,c3,c4), where tm=c4. The algorithm outputs a new ciphertext C′=(w1,w2,w3,w4), where
(6)w1=c3e^(s1,c2)e^(s0,(c1)c4),w2=c1,w3=c4,w4=s2.
Once delegatee receives the reencrypted ciphertext, he/she can obtain the plaintext by computing
(7)M=w1e^((w2)w3,Decrypt(w4,did′))-1=c3(e^(s1,c2)/e^(y0v,(c1)c4))e^((c1)c4,Decrypt(s2,did′))-1=c3(e^(s1,c2)/e^(y0,(c1)c4)·e^(v,(c1)c4))e^((c1)c4,Decrypt(s2,did′))-1=(Me^(g1,g2)rtme^(gx,g1idrtm)e^(g2α(g1idx),grtm)·e^(v,grtm))×(e^(grtm,v)-1)-1=(Me^(g,g2)αrtm·e^(g,g1)idxrtme^(g2,g)αrtm·e^(g1,g)idxrtm·e^(v,grtm))×(e^(grtm,v)-1)-1=M/e^(v,grtm)e^(v,grtm)-1=M.


## 3.2. Security Analysis

Theorem 9.
Suppose that the(k,t,ε-) dBDH assumption holds in G. Then, the proposed tm-IB-PRE scheme is (k,t′,q,ε′) selective identity (IND-sID-CPA) secure for any q, k, ε′≤ε and t′=t-Θ(τq), where τ is maximum time for an exponentiation in G.Proof.
LetA be an adversary against the proposed tm-IB-PRE scheme in the IND-sID-CPA sense. We construct an adversary B which solves the dBDH problem in G by utilizing A. Algorithm B is given (g,J1,J2,J3,U)=(g,ga,gb,gc,U) as input, where U=e^(g,g)abc or U=X∈RG1 and a,b,c∈RZp*. Algorithm B works by interacting with A in a selective identity game as follows.
Initialization. The selective identity game begins with A outputting a target identity id* and some fixed tm*.
Setup. To generate system parameters, algorithm B(i)
picksβ∈RZp*;(ii)
setsg1=J1 and g2=J2 and gives parameters params=(g,g1,g2) to A. The corresponding master key unknown to B is g2a=gab.
Phase 1. Taking parametersparams as input, the adversary adaptively issues the following queries.
Private Keyqueries.
A queries with any identifier idi≠id*. B outputs private keys didi corresponding to idi and sends it to A. Here,
(8)didi=(y0,y1)=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,g2-1/(idi-id*)gri(g2(-β)/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,),whereri∈RZp*.
Let x=ri-(b/(id-id*)); then didi is valid private key for idi. This is because
(9)didi=(y0,y1)=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,g2-1/(idi-id*)gri(g2(-β)/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri,),whereri∈RZp*=(g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri(g1idi)b/(idi-id*),gri-(b/(idi-id*))g2-β/(idi-id*)(g1idi-id*gβ)ri(g1-id*gβ)-ri(g1idi)(b)/(idi-id*))=(g2a(g1id)ri(g1-id*gβ)ri(g1-id*gβ)-ri(g1idi)b/(idi-id*),gri-(b/(idi-id*))g2a(g1id)ri(g1-id*gβ)ri(g1-id*gβ)-ri(g1idi)(b)/(idi-id*))=(g2a(g1id)ri(g1idi)b/(idi-id*),gri-(b/(idi-id*)))=(g2a(g1id)ri-(b/(idi-id*)),gri-(b/(idi-id*)))=(g2a(g1id)x,gx).
P
e
x
t
r
a
c
t
T
I
B
-
P
R
E
.
A queries with (id,id′,tm). If id≠id* (in this case, id′ can be any identity), the simulator B first simulates KeyGen(params,mk,id) as above and gets did. Then, it runs Pextract(params,did,id′,tm) and returns the resulting reencryption key rkid→id′ to the adversary. Otherwise, if id=id*, B rejects the query.
Preenc.
A queries the challenger with (M,id,id′,tm′). B only faithfully responds to this query if id≠id* and tm′≠tm*. Otherwise, B halts.
Once adversary decides that phase 1 is over, it selects two equal length plaintextsM0, M1∈M on which it wishes to be challenged.
Challenge. The challenger picks a random bit b∈R{0,1} and sets the challenge ciphertext to C*=(c1*,c2*,c3*,c4*)=(₭1,(₭2β)c4*, MbUc4*, c4*), where c4*=tm*. B returns C* to the adversary. Note that if U=e^(g,g)abc=e^(g1,g2)c, then C* is valid encryption of Mb. Otherwise, if U is uniform and independent in G1, then Mb is also independent of b in the adversary’s view.
Phase 2. The adversary issue further queries A and B responds as in phase 1.
Guess. Finally, A outputs a guess b′∈R{0,1}. Algorithm B concludes its own game by outputting a guess as follows. If b=b′, then B outputs 1 meaning U=e^(g,g)abc. Otherwise, it outputs 0 meaning U≠e^(g,g)abc.
B can perfectly simulate the reencryption key for id since it looks random and independent of any other values if A does not obtain the corresponding private key for id. When U=e^(g,g)abc, then A’s advantage is the same as B’s advantage for solving dBDH problem.


## 4. Conclusion

In this paper, a time-and-identity based proxy reencryption scheme based on BB-IBE and Matsuo’s PRE scheme has been proposed. Our scheme incorporates concept of time and gives the delegator the flexibility to categorize his/her message into subsets based on some defined time period. We have proven our scheme to be selective identity, chosen plaintext attack (IND-sID-CPA) secure in the standard model based on the decisional BDH assumption in the bilinear groups. Using only one key pair, the delegator in the scheme can provide the proxy with differentiated reencryption capabilities. This work can also be extended and included in various other fields [28–32] including m2m, IoT, and big data.



---

*Source: 329198-2014-05-22.xml*