# Provably Secure Security-Enhanced Timed-Release Encryption in the Random Oracle Model

Authors: Ke Yuan; Yahui Wang; Yingming Zeng; Wenlei Ouyang; Zheng Li; Chunfu Jia
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Cryptographic primitive of timed-release encryption (TRE) enables the sender to encrypt a message which only allows the designated receiver to decrypt after a designated time. Combined with other encryption technologies, TRE technology is applied to a variety of scenarios, including regularly posting on the social network and online sealed bidding. Nowadays, in order to control the decryption time while maintaining anonymity of user identities, most TRE solutions adopt a noninteractive time server mode to periodically broadcast time trapdoors, but because these time trapdoors are generated with fixed time server’s private key, many “ciphertexts” related to the time server’s private key that can be cryptanalyzed are generated, which poses a big challenge to the confidentiality of the time server’s private key. To work this out, we propose a concrete scheme and a generic scheme of security-enhanced TRE (SETRE) in the random oracle model. In our SETRE schemes, we use fixed and variable random numbers together as the time server’s private key to generate the time trapdoors. We formalize the definition of SETRE and give a provably secure concrete construction of SETRE. According to our experiment, the concrete scheme we proposed reduces the computational cost by about 10.8% compared to the most efficient solution in the random oracle model but only increases the almost negligible storage space. Meanwhile, it realizes one-time pad for the time trapdoor. To a large extent, this increases the security of the time server’s private key. Therefore, our work enhances the security and efficiency of the TRE.


---

## Body

## 1. Introduction

Cryptographic primitive of timed-release encryption (TRE) [1, 2] requires the sender to set a specified time for the designative receiver to decrypt the secret message. With TRE, the sender encrypts a message and then sends to the receiver; before the decrypt time that the sender has set arrives, no one can decrypt this ciphertext. With the efforts of many distinguished scholars, TRE has developed into a basic cryptographic primitive, which can be combined with many other cryptographic primitives and applied to different fields, such as regularly posting on the social network [3, 4], edge caching [5], and ciphertext retrieval [6, 7].According to the latest research, the TRE constructions have been extended from the mathematical problems [8–28] to the physical problems [29, 30] and the blockchain approach [31–34]. At present, a large number of TRE constructions are based on the mathematical problems. In practical terms, the most commonly used model is the noninteractive time server model. In this model, for the time server, neither the sender nor the receiver of the message interacts with it. The time server periodically broadcasts the time trapdoor. The receiver chooses the time trapdoor corresponding to the decryption time of the ciphertext to complete the decryption at the designated time.However, in the current noninteractive TRE schemes, many time trapdoors related to the time server’s private key will be generated. This will cause the attacker to have a certain amount of pairs (time, time trapdoor). Although the problems related to bilinear pairing are difficult to solve, the attacker can still adopt chosen-plaintext attack (CPA) or chosen-ciphertext attack (CCA) to attack the system, which seriously challenges the security of the private key of the time server. Thus, in this paper, we are working on this problem and trying to construct a solution.


### 1.1. Related Work

TRE was first proposed by May [2] in 1993 and then discussed in detail by Rivest et al. [1] in 1996. Most of the previous schemes can be divided into time-lock puzzles [1, 15, 18, 33] and agents categories. Most agent-class schemes use the time server as the agent, which are divided into interactive model [1, 8, 23, 24] and noninteractive model [9–14, 16, 17, 19–22, 25, 26, 28]. The time server method was originally constructed based on the quadratic residue problem [8]. After that, most of the proposed solutions are based on the assumption of the difficult bilinear pairing class problems, such as bilinear Diffie–Hellman (BDH) assumption [9–11, 13, 19, 21, 22, 24–28], bilinear Diffie–Hellman inversion (BDHI) assumption [12], and bilinear Diffie–Hellman exponent (BDHE) assumption [17].In the solutions of the noninteractive server model, the time server’s private key is used to perform an encryption-like operation on the hash function value of a time pointT to generate a corresponding time trapdoor. Therefore, this model produces many pairs (plaintext, ciphertext) related to the private key of the time server. In response to this problem, we need to construct a new solution.


### 1.2. Our Contributions

We reexamine the noninteractive time server model in which the time server’s private key is repeatedly used, resulting in many pairs (plaintext, ciphertext) related to the private key of the time server. In order to solve this problem, we construct a security-enhanced timed-release encryption (SETRE) solution based on the BDH assumption.As we all know, in the operations of encryption and decryption, we use the private keyk to encrypt the plaintext M and get the ciphertext C=EkM and use the private key k to decrypt the ciphertext C and get the plaintext M=DkC. Similarly, we let the private key s and the hash function value HT of a time point T perform some operations together to generate the corresponding time trapdoor ST=EsHT; correspondingly, we can get HT=DsST. In the above statement, ST is equivalent to the ciphertext C, and HT is equivalent to the plaintext M. If the attacker has many pairs (plaintext, ciphertext), then the security of the time server’s private key will be greatly threatened.Our SETRE schemes include a concrete scheme and a generic scheme. In our SETRE, the time server will use a random numberx as the time server’s session private key every time before publishing the time trapdoor. This session private key is combined with the time server’s fixed private key to generate the time trapdoor ST=Es,xHT of our SETRE. Therefore, in our SETRE schemes, the secret private key involved in every generated time trapdoor is different. So, we can claim that our schemes realize one-time pad for the time trapdoor. In this case, the attacker can only get a pair of (plaintext, ciphertext) about the time point and its time trapdoor at most. Even if the attacker successfully obtains the private key of the time server corresponding to a time trapdoor, he cannot get the private key of the time server corresponding to other time trapdoors so that the time trapdoor cannot be generated in advance, which ensures that the receiver cannot decrypt in advance.


### 1.3. Organization

We begin by explaining what is SETRE. In Section2, we give some cryptographic background and our generic public key encryption scheme. In Section 3, we formally define our SETRE and its simulation security game model. In Section 4, we present the concrete construction of SETRE and give its provably secure proof and the efficiency analysis. In Section 5, we provide the formal definition and construction of the generic SETRE and give its security analysis and efficiency analysis. Finally, we give the conclusion and future work.


## 1.1. Related Work

TRE was first proposed by May [2] in 1993 and then discussed in detail by Rivest et al. [1] in 1996. Most of the previous schemes can be divided into time-lock puzzles [1, 15, 18, 33] and agents categories. Most agent-class schemes use the time server as the agent, which are divided into interactive model [1, 8, 23, 24] and noninteractive model [9–14, 16, 17, 19–22, 25, 26, 28]. The time server method was originally constructed based on the quadratic residue problem [8]. After that, most of the proposed solutions are based on the assumption of the difficult bilinear pairing class problems, such as bilinear Diffie–Hellman (BDH) assumption [9–11, 13, 19, 21, 22, 24–28], bilinear Diffie–Hellman inversion (BDHI) assumption [12], and bilinear Diffie–Hellman exponent (BDHE) assumption [17].In the solutions of the noninteractive server model, the time server’s private key is used to perform an encryption-like operation on the hash function value of a time pointT to generate a corresponding time trapdoor. Therefore, this model produces many pairs (plaintext, ciphertext) related to the private key of the time server. In response to this problem, we need to construct a new solution.


## 1.2. Our Contributions

We reexamine the noninteractive time server model in which the time server’s private key is repeatedly used, resulting in many pairs (plaintext, ciphertext) related to the private key of the time server. In order to solve this problem, we construct a security-enhanced timed-release encryption (SETRE) solution based on the BDH assumption.As we all know, in the operations of encryption and decryption, we use the private keyk to encrypt the plaintext M and get the ciphertext C=EkM and use the private key k to decrypt the ciphertext C and get the plaintext M=DkC. Similarly, we let the private key s and the hash function value HT of a time point T perform some operations together to generate the corresponding time trapdoor ST=EsHT; correspondingly, we can get HT=DsST. In the above statement, ST is equivalent to the ciphertext C, and HT is equivalent to the plaintext M. If the attacker has many pairs (plaintext, ciphertext), then the security of the time server’s private key will be greatly threatened.Our SETRE schemes include a concrete scheme and a generic scheme. In our SETRE, the time server will use a random numberx as the time server’s session private key every time before publishing the time trapdoor. This session private key is combined with the time server’s fixed private key to generate the time trapdoor ST=Es,xHT of our SETRE. Therefore, in our SETRE schemes, the secret private key involved in every generated time trapdoor is different. So, we can claim that our schemes realize one-time pad for the time trapdoor. In this case, the attacker can only get a pair of (plaintext, ciphertext) about the time point and its time trapdoor at most. Even if the attacker successfully obtains the private key of the time server corresponding to a time trapdoor, he cannot get the private key of the time server corresponding to other time trapdoors so that the time trapdoor cannot be generated in advance, which ensures that the receiver cannot decrypt in advance.


## 1.3. Organization

We begin by explaining what is SETRE. In Section2, we give some cryptographic background and our generic public key encryption scheme. In Section 3, we formally define our SETRE and its simulation security game model. In Section 4, we present the concrete construction of SETRE and give its provably secure proof and the efficiency analysis. In Section 5, we provide the formal definition and construction of the generic SETRE and give its security analysis and efficiency analysis. Finally, we give the conclusion and future work.


## 2. Preliminary

We give a brief review of the bilinear pairing property, BDH assumption, and our generic public key encryption scheme that needs to be known in this section.


### 2.1. Properties of Bilinear Pairings

We give a form of bilinear pairings and their properties as described below.Definition 1.
LetG1 be an elliptic curve discrete logarithm problem (ECDLP) additive group over a finite field, G2 be a discrete logarithm problem (DLP) multiplicative group over a finite field, and the order of G1,G2 be a prime number q. The mapping e:G1×G2⟶G2 is a bilinear pairing mapping if e satisfies(1)
Bilinear property: given anyP,Q,R∈G1, the following operations hold:(1)eP+Q,R=eP,ReQ,R,eP,Q+R=eP,QeP,R.(2)
Nondegeneracy: suppose that the generator of groupG1 is P, then the generator of group G2 is eP,P.(3)
Computability: given any two elementsP,Q∈G1, there must be an effective algorithm for calculating eP,Q.


### 2.2. BDH Assumption

Many cryptographic schemes are based on various difficult assumptions related to bilinear pairs, such as the (D)BDH assumption, (D)BDHI assumption, and (D)BDHE assumption [35, 36]. We now give the definition of the BDH assumption used in our SETRE schemes as follows.Definition 2.
LetG1 be an ECDLP additive group over a finite field, P be the generator of G1, G2 be a DLP multiplicative group over a finite field, and the order of G1,G2 be a prime number q. Given P,aP,bP,cP∈G1∗ (a,b, and c are evenly distributed in ℤq∗), calculate eP,Pabc∈G2∗. If PrAP,aP,bP,cP=eP,Pabc≥E, then the advantage of the adversary A to solve the BDH assumption is E, and E is negligible.


### 2.3. General Public Key Encryption Scheme

We simplify and abstract public key encryption (which has a certain characteristic) and only keep three phases which are initialization, encryption, and decryption; then, the general public key encryption (GPKE) scheme can be obtained.Definition 3.
EGPKE=Setup,Enc,Dec is the public key encryption algorithm, whereSetup: generates system public parameters and the user’s public key and private key pairsupk,usk=uP,u in which u∈ℤq∗,P∈G1 is a generator of G1, and G1 is an additive groupEnc: uses the user’s public keyuP to encrypt the plaintext to get the ciphertext CGPKE=EncM,uPDec: uses the user’s private keyu to decrypt the ciphertext to get the plaintext M=DecCGPKE,u


## 2.1. Properties of Bilinear Pairings

We give a form of bilinear pairings and their properties as described below.Definition 1.
LetG1 be an elliptic curve discrete logarithm problem (ECDLP) additive group over a finite field, G2 be a discrete logarithm problem (DLP) multiplicative group over a finite field, and the order of G1,G2 be a prime number q. The mapping e:G1×G2⟶G2 is a bilinear pairing mapping if e satisfies(1)
Bilinear property: given anyP,Q,R∈G1, the following operations hold:(1)eP+Q,R=eP,ReQ,R,eP,Q+R=eP,QeP,R.(2)
Nondegeneracy: suppose that the generator of groupG1 is P, then the generator of group G2 is eP,P.(3)
Computability: given any two elementsP,Q∈G1, there must be an effective algorithm for calculating eP,Q.


## 2.2. BDH Assumption

Many cryptographic schemes are based on various difficult assumptions related to bilinear pairs, such as the (D)BDH assumption, (D)BDHI assumption, and (D)BDHE assumption [35, 36]. We now give the definition of the BDH assumption used in our SETRE schemes as follows.Definition 2.
LetG1 be an ECDLP additive group over a finite field, P be the generator of G1, G2 be a DLP multiplicative group over a finite field, and the order of G1,G2 be a prime number q. Given P,aP,bP,cP∈G1∗ (a,b, and c are evenly distributed in ℤq∗), calculate eP,Pabc∈G2∗. If PrAP,aP,bP,cP=eP,Pabc≥E, then the advantage of the adversary A to solve the BDH assumption is E, and E is negligible.


## 2.3. General Public Key Encryption Scheme

We simplify and abstract public key encryption (which has a certain characteristic) and only keep three phases which are initialization, encryption, and decryption; then, the general public key encryption (GPKE) scheme can be obtained.Definition 3.
EGPKE=Setup,Enc,Dec is the public key encryption algorithm, whereSetup: generates system public parameters and the user’s public key and private key pairsupk,usk=uP,u in which u∈ℤq∗,P∈G1 is a generator of G1, and G1 is an additive groupEnc: uses the user’s public keyuP to encrypt the plaintext to get the ciphertext CGPKE=EncM,uPDec: uses the user’s private keyu to decrypt the ciphertext to get the plaintext M=DecCGPKE,u


## 3. SETRE: Definitions

Suppose Bob is a social network user, and he wants to upload documents scheduled to be published regularly to the social network platform in advance so that he can pay attention to other things without worrying about this matter. And Bob does not want the social network platform to know in advance what he wants to publish. In this application scenario, Bob can use our SETRE solution to solve this problem securely and efficiently. Bob sends the following ciphertext of the document in advance with the designated decryption time:(2)C=EncM,tspub,tsspub,upk,r,T,where M is one of the documents planned to be released at a designated time point in the future, tspub and tsspub are the time server’s fixed public key and session public key, respectively, upk is the receiver’s public key, r is a random number as a factor of freshness, and T is the designated decryption time. The social network platform can obtain the ciphertext of the document in advance but can only decrypt it in the future after the predetermined decryption time has arrived. We call such a cryptographic scheme noninteractive SETRE.Definition 4.
Our noninteractive concreteSETRE scheme includes three entities which are time server, sender, and receiver and polynomial-time randomized algorithm 7 tuples ESETRE=Setup,TS_KeyGen,User_KeyGen,Enc,ST_Rel,ST_Rel,Dec, whereSetup: generates a public parameter params from a security parameterTS_KeyGen: calculates and generates the fixed public/private key pair tspub,tspriv and the session public/private key pair tsspub,tsspriv of the time serverUser_KeyGen: calculates and generates the public/private key pair upk,usk of the system userEnc: calculates the ciphertext C of the plaintext M, by using the public keys tspub,tsspub, and upk, and a designated decryption time point TST_Rel: calculates a time server’s time trapdoor ST, by using the time server’s fixed private key tspriv, a designated decryption time point T, and its corresponding session private key tssprivUT_Rel: calculates a user’s time trapdoor UT, by using the receiver’s private key usk and a designated decryption time point TDec: calculates a plaintext M, by using a ciphertext C, the time server’s time trapdoor ST, and the receiver’s time trapdoor UT; or outputs a “reject” message
We use the simulation security game between the adversaryA and the challenger ℬ to formally define the security against the active adversary A. The specific formal definition is as follows:Preparation: public parameters are generated by the system.Initialization: a pair of designated decryption time pointsT0∗ and T1∗ to be challenged is selected by the adversary A.Setup: the public parametersparams and public keys upk, tspub, and tsspub are generated by the challenger ℬ and sent to the adversary A.Phase 1: the adversaryA performs m queries of q1,q2,…,qm, where query qi is one of the following:(1)
At any time point, the adversaryA can perform queries of the random oracles H1 and H2. In response to H1 and H2 queries, the challenger ℬ keeps two lists of H1-list and H2-list.(2)
Time trapdoor queries: time trapdoor querySTi and UTi of Ti where Ti∉T0∗,T1∗. The challenger ℬ responds by running algorithm ST_Rel and UT_Rel to generate the time trapdoors STi and UTi corresponding to the designated decryption time point Ti. The challenger ℬ then sends STi and UTi to the adversary A.(3)
Decryption queries: decryption queryCi,Ti for the designated decryption time point Ti. To decrypt the ciphertext Ci,Ti, ℬ runs algorithm Dec and uses the time trapdoors STi and UTi. The challenger ℬ then sends the decrypted plaintext M to the adversary A.These queries can be adaptive, which means that the response ofqi can be determined based on the responses of q1,q2,…,qi−1 previously queried.Challenge: a pair of designated decryption time pointsT0∗ and T1∗ to be challenged is selected by the adversary A. The challenger ℬ selects a random bit ♭∈0,1, sets the ciphertext to be C♭∗,T♭∗, and then sends the challenge ciphertext C♭∗,T♭∗ to A.Phase 2: the adversaryA performs other queries of qm+1,…,qnum, and the challenger ℬ responds as shown in Phase 1.Guess: in the end, the adversaryA outputs a guess of ♭′∈0,1. If ♭=♭′, then A wins the simulation security game.
We call such an adversaryA an IND-sT-CCA adversary, and we can formally define the advantages of A attack our concrete SETRE scheme E as(3)AdvE,ACCA=Pr♭=♭′−12.Definition 5.
Our concrete SETRE schemeE is said to be t,qH2,qT,qC,ɛ-selective designated decryption time, adaptive chosen-ciphertext secure if for any t-time IND-sT-CCA adversary A that performs at most qH2H2 queries, qT chosen designated decryption trapdoor queries, and qC chosen decryption queries, we have that AdvE,ACCA<ɛ. In other words, we call that E is t,qH2,qT,qC,ɛ IND-sT-CCA secure.
We define our concrete SETRE schemeE to be IND-sT-CPA secure by simply disallowing the adversary A to perform decryption queries in the simulation security game described above.Definition 6.
Our concrete SETRE schemeE is said to be t,qT,ɛ-selective designated decryption time, adaptive chosen-plaintext secure if E is t,qH2,qT,0,ɛ-selective designated decryption time, chosen-ciphertext secure. In other words, we call that E is t,qH2,qT,ɛ IND-sT-CPA secure.


## 4. Concrete Scheme of SETRE

We will attempt to propose a concrete scheme of SETRE based on the BDH assumption in the random oracle model.


### 4.1. Construction

The server-passive, scalable, user-anonymous TRE scheme proposed by Black and Chan (abbreviated as BC-TRE) laid the foundation of TRE. We now describe the concrete SETRE construction scheme. The scheme includes the following algorithm 7 tuples:Setup: generates a public parameterparams=G1,G2,q,e,P,H1,H2,n from a security parameter k, where G1 is an ECDLP additive group over a finite field, G2 is a DLP multiplicative group over a finite field, and the order of G1,G2 is a prime number q, e:G1×G1⟶G2 is a bilinear mapping that satisfies Definition 1, P∈G1∗ is the generator of additive group G1, and H1:0,1∗⟶G1 and H2:G2⟶0,1n (n is the length of the plaintext) are hash functions.TS-KeyGen: the time server selects a random numbers∈ℤq∗ as the private key tspriv=s∈ℤq∗ of the time server and then calculates and generates the time server’s public key tspub=sP. Similarly, the time server selects a random number set as the session private key set TSspriv=x1,x2,…,xl∈ℤq∗ of the time server and then calculates and generates the corresponding time server’s session public key set TSspub=x1P,x2P,…,xlP∈G1∗ in which l≈175200 if we assume that a time trapdoor needs to be generated every half an hour and meet the demand for 10 consecutive years.User-KeyGen: a user selects a random numberu∈ℤq∗ as its private key usk=u∈ℤq∗ and then calculates and generates the system user’s public key upk=uP.Enc: the sender uses the public keyupkr=uP of the receiver, the public key tspub=sP of the time server, a designated decryption time point T∈0,1∗, and the time server’s session public key tsspub=xP corresponding to the designated decryption time point T∈0,1∗ to encrypt the plaintext M as the following operations:(1)
Selects a random numberr∈ℤq∗ and calculates U=rP(2)
CalculatesSpub=upk+tspub+tsspub=uP+sP+xP=u+s+xP(3)
CalculatesK=eSpub,rH1T=eP,H1Tru+s+x(4)
Outputs the ciphertextC(4)C=U,V=rP,M⊕H2K.TS-Rel: the time server takes its own fixed private keytspriv=s and the session private key tsspriv=x of the current release time T and produces the time server’s time trapdoor ST=s+xH1T.UT_Rel: the receiver takes the private keyusk=u of his own and the current designated decryption time T and produces the user’s time trapdoor UT=uH1T.Dec: the receiver uses the time trapdoorsST and UT of the designated decryption time point T∈0,1∗ to decrypt the ciphertext C=U,V as the following operations:(1)
CalculatesK′=eU,ST+UT(2)
CalculatesV⊕H2K′ to recover the corresponding plaintext MSupposeC is the valid ciphertext; then, we have U=rP and V=M⊕H2K. We can verify the correctness of the decryption as described in the following:(5)K′=eUT+ST,U=euH1T+s+xH1T,rP=eu+s+xH1T,rP=eH1T,Pru+s+x=K,V⊕H2K′=V⊕H2K=M⊕H2K⊕H2K=M.


### 4.2. Security of the Scheme

We give the proof that our SETRE scheme is noninteractive and semantically secure against CPA in the random oracle model, supposing that the BDH assumption is true [37].Theorem 1.
Suppose that there is an adversaryA who can break our SETRE scheme with the advantage of ϵ; then, a challenger ℬ, who can overcome the BDH problem with probability at least ɛ′=ɛ/eqTqH2, is constructed, where e is the natural logarithm’s base and qT and qH2 are the maximum number of times we assume the adversary A can query the time trapdoor and H2 hash operation.Proof.
LetA denote an adversary who has advantage ϵ to break the SETRE. Assume that A performs no more than qH2 hash operation queries to H2, no more than qT user trapdoors, and the time server trapdoor queries, where qT and qH2 are positive. Let ℬ denote a challenger who overcomes the BDH problem with probability no less than ɛ′=ɛ/eqH2qT. Therefore, if the BDH assumption holds in G1, then we can ignore ɛ′; furthermore, the advantage of A to break the SETRE can be ignored. And ℬ, who simulates as the challenger, will interact with adversary A as follows:Preparation: letG1 be an ECDLP additive group over a finite field, G2 be a DLP multiplicative group over a finite field, the order of G1,G2 be a prime number q, e:G1×G1⟶G2 be a bilinear mapping that satisfies Definition 1, and P∈G1∗ be the generator of additive group G1. Give the challenger ℬ the public parameter P, P1=aP=uP+sP+xP, P2=bP, and P3=cP∈G1; the goal of ℬ is to calculate the value of v=eP,Pabc∈G2, where a,b,c∈Zq∗.Initialization: the adversaryA outputs a pair of designated decryption time points T0∗ and T1∗ to be challenged.Setup: the challengerℬ gives A the public keys upkr=uP, tspub=sP, and tsspub=xP.Phase 1: the adversaryA initiates 1,…,m queries, and ℬ gives the response, respectively, where for the i-th query, ℬ’s response is described as follows:(1)
H1 and H2 queries: every point in time, the adversary A can perform queries of the random oracles H1 and H2. In response to H1 queries, the challenger ℬ keeps a list of quadruples Tj,hj,mj,nj, which we will call it the H1-list and is initially set to be empty. If A performs a query of H1 at a time point Ti∈0,1∗, then ℬ gives the response as follows:①
If the query aboutTi has been made before, then ℬ takes H1Ti=hi∈G1 as its response.②
If not,ℬ chooses a new random bit ni∈0,1 to satisfy Prni=0=1/qs+1.③
ℬ takes a random number mi∈Zp.Ifni=0 holds, ℬ calculates hi←P2+mi⋅P∈G1.Ifni=1 holds, ℬ calculates hi←mi⋅P∈G1.④
ℬ adds the quadruple Ti,hi,mi,ni to the H1-list and takes H1Ti=hi∈G1 as its response to A.In the same way,A can perform a query to H2 at any point in time. The H2-list is initially set to be empty. ℬ gives the response to the query on H2Ki by selecting a new random Vi∈0,1log2p as the value of H2Ki for every new Ki and adding the tuple Ki,Vi to H2-list. If H2-list already contains Ki,Vi, then ℬ takes Ki,Vi from H2-list and returns it to A as the response value.(2)
Time trapdoor queries: if the adversaryA performs queries of the time trapdoor at a time point Ti∉T0∗,T1∗, then the challenger ℬ gives the response as follows:①
ℬ runs the above H1 query algorithm and obtains H1Ti=hi∈G1 and makes Ti,hi,mi,ni as the corresponding entry in H1-list.②
Ifni=0, then ℬ aborts the simulation security game and admits failure.③
Ifni=1, we obtain hi=mi⋅P∈G1. Let Tui=mi⋅upkr and TTi=mi⋅tspub+tsspub; then, we can transform them to get Tui=uH1Ti and TTi=s+xiH1Ti. Therefore, Tui is the correct and legal user time trapdoor of Ti, and TTi is the correct and legal time server trapdoor of Ti. ℬ gives Tui and TTi to A.Challenge: the adversaryA selects a pair of designated decryption time points T0∗,T1∗ to be challenged. The challenger ℬ produces the challenge ciphertext as follows:①
The challengerℬ runs the above H1 query algorithm twice to obtain h0∗ and h1∗∈G1 which satisfy H1T0∗=h0∗ and H1T1=h1∗.②
Fori=0,1, we let T0∗,h0∗,m0∗,n0∗ and T1∗,h1∗,m1∗,n1∗ to be the corresponding tuples on the H1-list. If n0′=n1′=1, then the challenger ℬ aborts the simulation security game and admits failure.③
Obviously, at least one ofn0∗ and n1∗ must be equal to zero. ℬ randomly takes ♭∈0,1 such that n♭=0.④
ℬ takes the challenge ciphertext C♭∗=P3,J for random J∈0,1log2p as its response. Obviously, this challenge implicitly defines H2eH1T♭∗,c⋅upkr⋅eH1T♭∗,c⋅tspub⋅eH1T♭∗,c⋅tsspub♭=J. That is to say,(6)J=H2ecH1T♭∗,upkr+tspub+tsspub♭=H2eP2+m♭∗P,u+s+x♭Pc=H2eP,Pcu+s+x♭b+m♭∗.It can be seen thatC♭∗ is the corresponding valid and real ciphertext for T♭∗.Phase 2: the adversaryA performs other queries of qm+1,…,qnum, and the challenger ℬ responds as shown in Phase 1.Guess: in the end, the adversaryA outputs a guess of ♭′∈0,1 to indicate whether the challenge ciphertext C♭∗ is a valid ciphertext for Encupkr,tspub,tsspub0,T0∗ or Encupkr,tspub,tsspub1,T1∗. Now, the challenger ℬ randomly selects a tuple Kj,Vj from the H2-list and outputs K/eupkr,tspub,tsspub♭,P3m♭∗ as a guess of eP,Pabc. If A has ever inquired about one of H2ecH1T0∗,upkr+tspub+tsspub0 or H2ecH1T1∗,upkr+tspub+tsspub1, the H2-list has a probability of 1/2 that contains Kj,Vj, Kj=H2ecH1T♭∗,upkr+tspub+tsspub♭=H2eP,Pcu+s+x♭b+m♭∗. If ℬ takes this tuple Kj,Vj from the H2-list, then K/eupkr,tspub+tsspub♭,P3m♭∗=eP,Pabc.
The whole security simulation game is completed here. Next, we calculate the value ofϵ′ which is the lowest probability of ℬ correctly outputting eP,Pabc. It is easy to know that the premise that it can correctly output its guess value of eP,Pabc is that the game can continue to the guessing stage without terminating the game in the middle. Now, we analyze the possibility that ℬ does not terminate the game while the game is in progress. For this purpose, we first give the definition of the following events:E0: in the stage when the adversary A performs queries of the time trapdoor, the challenger ℬ does not terminate the simulation security gameE1: in the challenge stage, the challenger ℬ does not terminate the simulation security game
We first state that, as in [38], events E1 and E2 occur with a high enough probability. Next, we give the following three claims.Claim 1: in the stage when the adversary A performs queries of the time trapdoor, the probability that the challenger ℬ does not terminate the simulation security game is 1/e at least. Thus, PrE0≥1/e.Proof.
When the adversaryA queries for the time trapdoor of time points, for the sake of generality, we suppose that A does not query the same time trapdoor twice. A trapdoor (the user’s time trapdoor or the time server’s time trapdoor) query causes ℬ to terminate the simulation security game with a probability of 1/qT+1; therefore, a trapdoor query does not cause ℬ to terminate the game with a probability of 1−1/qT+1. In addition, since the maximum number of times A can query the time trapdoor is qT, the probability that the simulation security game will not be terminated after qT queries is 1−1/qT+1qT≥1/e at least.Claim 2: in the challenge stage, the probability that the challenger ℬ does not terminate the simulation security game is 1/qT at least. Thus, PrE1≥1/qT.Proof.
If the adversaryA can generate T0∗, T1∗ with the property n0∗=n1∗=1, then the challenger ℬ will terminate the simulation security game during the challenge stage. Since A has not queried for the trapdoor for T0∗, T1∗, we have that n0∗,n1∗ are independent of A. Therefore, Prn♭∗=0=1/qT+1 for ♭=0,1, and then we have that Prn0∗=n1∗=1=1−1/qT+12≤1−1/qT. Therefore, there is a probability of at least 1/qT that ℬ does not terminate the game.Since the adversaryA is not allowed to query the time trapdoor of the designated decryption time T0,T1 during the game, the events E0 and E1 are independent of each other, so we can get PrE0∩E1≥1/eqT.Assume that the adversaryA has acquired the public keys upkr=uP, tspub=sP, and tsspub=xP in the actual attack game. The adversary A selects a pair of designated decryption time points T0∗,T1∗ to be challenged. The challenger ℬ produces the challenge ciphertext C♭∗=P3,J as a response. Therefore, we have the following Claim 3.Claim 3: in the actual attack game, the adversary A has at least the probability of ϵ to perform an H2 query for one of H2ecH1T0∗,upkr+tspub+tsspub0, H2ecH1T1∗,upkr+tspub+tsspub1.Before giving the proof, we first give the definition of the following events:E2: in the actual attack game, A does not query either H2ecH1T0∗,upkr+tspub+tsspub0 or H2ecH1T1∗,upkr+tspub+tsspub1E3: in the guess stage, A outputs the guess ♭′ of ♭ satisfying ♭=♭′Proof.
WhenE2 occurs, it is obvious that the bit ♭∈0,1 indicates whether C♭∗ is the challenge ciphertext corresponding to the designated decryption time, which has nothing to do with A’s knowledge. Thus, the probability of PrE3 is 1/2 at most. In the real attack game, because A has the advantage of ϵ, we have PrE3−1/2≥ɛ and Pr¬E2≥2ɛ. Now, we give the specific argument for the truth of Pr¬E2≥2ɛ as follows:(7)PrE3=PrE3|E2PrE2+PrE3|¬E2Pr¬E2≤PrE3|E2PrE2+Pr¬E2≤12PrE2+Pr¬E2≤12+12Pr¬E2PrE3≥PrE3|E2PrE2≥12PrE2≥12−12Pr¬E2.From the above two formulas, we know thatϵ≤PrE3−1/2≤1/2Pr¬E2. Thus, we have Pr¬E2≥2ɛ in the actual attack game.If the challengerℬ does not terminate the game, it means that, in the process of simulating the actual attack game, the adversary A has queried one of H2ecH1T0∗,upkr+tspub+tsspub0, H2ecH1T1∗,upkr+tspub+tsspub1. Thus, Pr¬E2≥2ϵ.Claim 4: the probability that the challenger ℬ can solve the BDH problem successfully in the guess stage is ϵ/qH2.Proof.
Assuming the event of Claim 3 occurs, the value of one of the two cases ofecH1T♭∗,upkr+tspub+tsspub♭ will be stored in the H2-list. Consequently, in the guess stage, the challenger ℬ has at least the probability of 1/qH2 to select the correct pair from the H2-list. Therefore, on the premise that ℬ does not terminate the simulation game, the possibility that ℬ can successfully solve the BDH problem is ϵ/qH2.
According to Claims 1 and 2, during the simulation game, the probability that the challengerℬ will not terminate the game is at least 1/eqT. And according to Claim 4, if ℬ does not terminate the simulation security game, the probability that ℬ can successfully solve the BDH problem is ϵ/qH2. Therefore, through the security simulation game of the aforementioned adversary A and challenger ℬ, the possibility of successfully solving the BDH problem is ɛ/eqTqH2. Thus, Theorem 1 is proved.


### 4.3. Efficiency Analysis

We contrast between our SETRE scheme and two representative noninteractive time server TRE schemes: the classic BC-TRE scheme put forward by Blake and Chan [9] and the AnTRE scheme, which has highest efficiency up till now, put forward by Chalkias et al. [12].We letBP be a notation of the bilinear pairing operation, PAec and PMec be a notation of point addition and point multiplication operations in G1 separately. Let Expec be a notation of the exponentiation operation in G2 and Inv be a notation of the modular inverse operation in ℤq∗. Let H1 represent a hash function operation that maps binary strings of any length to an element in group G1, H2 represent the hash function operation that maps an element in group G2 to a string of log2q length 0 and 1, and H3 represent the hash function operation of mapping a binary string of any length to an element of ℤq∗. Based on the MIRACL large integer library, we program and implement the basic operations described above, in which the relevant parameters are set as follows: the elliptic curve is a supersingular elliptic curve E:y=x3+1 mod p on the finite field Fp (p is a 512-bit large prime number), and its prime order q is a 160-bit prime number; the bilinear map uses the Tate pairing algorithm to map the aforementioned discrete logarithm subgroup on the elliptic curve to the discrete logarithm subgroup on Fp2. The configuration of the running environment is as follows: Intel(R) Core(TM) i5-4210M @ 2.60 GHz microprocessors, 64 bit and 8 GB memory, Microsoft Visual Studio 2010. 987654321 is the seed that generates the associated random numbers. We take the calculation time of Expec as the basic unit so that the calculation results are not related to the specific computer performance. We then calculate and record the ratio of the calculation time of each related basic operation in these schemes to the calculation time of Expec, as shown in Table 1.Table 1
Calculation cost of related basic operations relative to theExpec operation.
Related basic operationsNotationRelative costBilinear pairingBP3.4457Point addition inG1PAec0.0072Point multiplication inG1PMec1Exponentiation inG2Expec0.3220Modular inverse inℤq∗Inv0.0030Hash function:0,1∗⟶G1H10.3368Hash function:G1⟶0,1log2qH20.0782Hash function:0,1∗⟶ℤq∗H30.0030In our SETRE scheme, the TS-Rel stage requires onePMec and one H1 to calculate ST=s+xH1T, and the total calculation cost of the TS-Rel stage is 1.003. The Enc stage requires one PMec for rP, two PAec for Spub, one H1, one PMec, and one BP for erH1T,Spub, and one H2 for H2K, and the total calculation cost of the Enc stage is 5.875. The Dec stage requires one H1, one PMec, one PAec, and one BP for K′=eU,ST+uH1T and one H2 for M⊕H2K, and the total calculation cost of the Dec stage is 4.868. We sum up the calculation cost of the schemes of BC-TRE, AnTRE, and our SETRE as shown in Table 2. It should be pointed out that the hash functions H1 and H2 in the scheme of AnTRE are approximately equivalent to H3 in Table 1, and the hash functions H3 and H4 in the scheme of AnTRE are approximately equivalent to H2 in Table 1.Table 2
Calculation cost of BC-TRE, AnTRE, and our SETRE.
SchemePhaseBC-TRE [9]AnTRE [12]Our SETRETS−RelPMec+H1=1.337PMec+Inv+H3=1.006PMec+H1=1.337Enc3BP+2PMec+H3=12.3404PMec+PAec+Expec+BP+2H2+2H3=7.9342PMec+2PAec+H1+BP+H2=5.875DecBP+Expec+H1+H2=4.183BP+PMec+2H2+H3=4.605H1+PMec+PAec+BP+H2=4.868Total17.8613.5512.08Table2 shows that our SETRE scheme has improved by 32.4% and 10.8%, respectively, compared with the schemes of BC-TRE and AnTRE. In addition, in the aspect of security, our SETRE scheme realizes one-time pad for the time trapdoor. Therefore, compared with the previous schemes, our SETRE greatly improves the security of the time server’s private key. In terms of storage, we need 160 bits of storage space for each private key of the time server and 1024 bits for each public key of the time server. Therefore, if it is assumed that the time server broadcasts a time trapdoor every half an hour and needs to store the session time server private key and public key for 10 years, then the additional storage space required by our scheme is 24∗2∗365∗10∗(1024 + 160)bit≈24.7 MB, which only adds almost negligible storage burden to the time server.


## 4.1. Construction

The server-passive, scalable, user-anonymous TRE scheme proposed by Black and Chan (abbreviated as BC-TRE) laid the foundation of TRE. We now describe the concrete SETRE construction scheme. The scheme includes the following algorithm 7 tuples:Setup: generates a public parameterparams=G1,G2,q,e,P,H1,H2,n from a security parameter k, where G1 is an ECDLP additive group over a finite field, G2 is a DLP multiplicative group over a finite field, and the order of G1,G2 is a prime number q, e:G1×G1⟶G2 is a bilinear mapping that satisfies Definition 1, P∈G1∗ is the generator of additive group G1, and H1:0,1∗⟶G1 and H2:G2⟶0,1n (n is the length of the plaintext) are hash functions.TS-KeyGen: the time server selects a random numbers∈ℤq∗ as the private key tspriv=s∈ℤq∗ of the time server and then calculates and generates the time server’s public key tspub=sP. Similarly, the time server selects a random number set as the session private key set TSspriv=x1,x2,…,xl∈ℤq∗ of the time server and then calculates and generates the corresponding time server’s session public key set TSspub=x1P,x2P,…,xlP∈G1∗ in which l≈175200 if we assume that a time trapdoor needs to be generated every half an hour and meet the demand for 10 consecutive years.User-KeyGen: a user selects a random numberu∈ℤq∗ as its private key usk=u∈ℤq∗ and then calculates and generates the system user’s public key upk=uP.Enc: the sender uses the public keyupkr=uP of the receiver, the public key tspub=sP of the time server, a designated decryption time point T∈0,1∗, and the time server’s session public key tsspub=xP corresponding to the designated decryption time point T∈0,1∗ to encrypt the plaintext M as the following operations:(1)
Selects a random numberr∈ℤq∗ and calculates U=rP(2)
CalculatesSpub=upk+tspub+tsspub=uP+sP+xP=u+s+xP(3)
CalculatesK=eSpub,rH1T=eP,H1Tru+s+x(4)
Outputs the ciphertextC(4)C=U,V=rP,M⊕H2K.TS-Rel: the time server takes its own fixed private keytspriv=s and the session private key tsspriv=x of the current release time T and produces the time server’s time trapdoor ST=s+xH1T.UT_Rel: the receiver takes the private keyusk=u of his own and the current designated decryption time T and produces the user’s time trapdoor UT=uH1T.Dec: the receiver uses the time trapdoorsST and UT of the designated decryption time point T∈0,1∗ to decrypt the ciphertext C=U,V as the following operations:(1)
CalculatesK′=eU,ST+UT(2)
CalculatesV⊕H2K′ to recover the corresponding plaintext MSupposeC is the valid ciphertext; then, we have U=rP and V=M⊕H2K. We can verify the correctness of the decryption as described in the following:(5)K′=eUT+ST,U=euH1T+s+xH1T,rP=eu+s+xH1T,rP=eH1T,Pru+s+x=K,V⊕H2K′=V⊕H2K=M⊕H2K⊕H2K=M.


## 4.2. Security of the Scheme

We give the proof that our SETRE scheme is noninteractive and semantically secure against CPA in the random oracle model, supposing that the BDH assumption is true [37].Theorem 1.
Suppose that there is an adversaryA who can break our SETRE scheme with the advantage of ϵ; then, a challenger ℬ, who can overcome the BDH problem with probability at least ɛ′=ɛ/eqTqH2, is constructed, where e is the natural logarithm’s base and qT and qH2 are the maximum number of times we assume the adversary A can query the time trapdoor and H2 hash operation.Proof.
LetA denote an adversary who has advantage ϵ to break the SETRE. Assume that A performs no more than qH2 hash operation queries to H2, no more than qT user trapdoors, and the time server trapdoor queries, where qT and qH2 are positive. Let ℬ denote a challenger who overcomes the BDH problem with probability no less than ɛ′=ɛ/eqH2qT. Therefore, if the BDH assumption holds in G1, then we can ignore ɛ′; furthermore, the advantage of A to break the SETRE can be ignored. And ℬ, who simulates as the challenger, will interact with adversary A as follows:Preparation: letG1 be an ECDLP additive group over a finite field, G2 be a DLP multiplicative group over a finite field, the order of G1,G2 be a prime number q, e:G1×G1⟶G2 be a bilinear mapping that satisfies Definition 1, and P∈G1∗ be the generator of additive group G1. Give the challenger ℬ the public parameter P, P1=aP=uP+sP+xP, P2=bP, and P3=cP∈G1; the goal of ℬ is to calculate the value of v=eP,Pabc∈G2, where a,b,c∈Zq∗.Initialization: the adversaryA outputs a pair of designated decryption time points T0∗ and T1∗ to be challenged.Setup: the challengerℬ gives A the public keys upkr=uP, tspub=sP, and tsspub=xP.Phase 1: the adversaryA initiates 1,…,m queries, and ℬ gives the response, respectively, where for the i-th query, ℬ’s response is described as follows:(1)
H1 and H2 queries: every point in time, the adversary A can perform queries of the random oracles H1 and H2. In response to H1 queries, the challenger ℬ keeps a list of quadruples Tj,hj,mj,nj, which we will call it the H1-list and is initially set to be empty. If A performs a query of H1 at a time point Ti∈0,1∗, then ℬ gives the response as follows:①
If the query aboutTi has been made before, then ℬ takes H1Ti=hi∈G1 as its response.②
If not,ℬ chooses a new random bit ni∈0,1 to satisfy Prni=0=1/qs+1.③
ℬ takes a random number mi∈Zp.Ifni=0 holds, ℬ calculates hi←P2+mi⋅P∈G1.Ifni=1 holds, ℬ calculates hi←mi⋅P∈G1.④
ℬ adds the quadruple Ti,hi,mi,ni to the H1-list and takes H1Ti=hi∈G1 as its response to A.In the same way,A can perform a query to H2 at any point in time. The H2-list is initially set to be empty. ℬ gives the response to the query on H2Ki by selecting a new random Vi∈0,1log2p as the value of H2Ki for every new Ki and adding the tuple Ki,Vi to H2-list. If H2-list already contains Ki,Vi, then ℬ takes Ki,Vi from H2-list and returns it to A as the response value.(2)
Time trapdoor queries: if the adversaryA performs queries of the time trapdoor at a time point Ti∉T0∗,T1∗, then the challenger ℬ gives the response as follows:①
ℬ runs the above H1 query algorithm and obtains H1Ti=hi∈G1 and makes Ti,hi,mi,ni as the corresponding entry in H1-list.②
Ifni=0, then ℬ aborts the simulation security game and admits failure.③
Ifni=1, we obtain hi=mi⋅P∈G1. Let Tui=mi⋅upkr and TTi=mi⋅tspub+tsspub; then, we can transform them to get Tui=uH1Ti and TTi=s+xiH1Ti. Therefore, Tui is the correct and legal user time trapdoor of Ti, and TTi is the correct and legal time server trapdoor of Ti. ℬ gives Tui and TTi to A.Challenge: the adversaryA selects a pair of designated decryption time points T0∗,T1∗ to be challenged. The challenger ℬ produces the challenge ciphertext as follows:①
The challengerℬ runs the above H1 query algorithm twice to obtain h0∗ and h1∗∈G1 which satisfy H1T0∗=h0∗ and H1T1=h1∗.②
Fori=0,1, we let T0∗,h0∗,m0∗,n0∗ and T1∗,h1∗,m1∗,n1∗ to be the corresponding tuples on the H1-list. If n0′=n1′=1, then the challenger ℬ aborts the simulation security game and admits failure.③
Obviously, at least one ofn0∗ and n1∗ must be equal to zero. ℬ randomly takes ♭∈0,1 such that n♭=0.④
ℬ takes the challenge ciphertext C♭∗=P3,J for random J∈0,1log2p as its response. Obviously, this challenge implicitly defines H2eH1T♭∗,c⋅upkr⋅eH1T♭∗,c⋅tspub⋅eH1T♭∗,c⋅tsspub♭=J. That is to say,(6)J=H2ecH1T♭∗,upkr+tspub+tsspub♭=H2eP2+m♭∗P,u+s+x♭Pc=H2eP,Pcu+s+x♭b+m♭∗.It can be seen thatC♭∗ is the corresponding valid and real ciphertext for T♭∗.Phase 2: the adversaryA performs other queries of qm+1,…,qnum, and the challenger ℬ responds as shown in Phase 1.Guess: in the end, the adversaryA outputs a guess of ♭′∈0,1 to indicate whether the challenge ciphertext C♭∗ is a valid ciphertext for Encupkr,tspub,tsspub0,T0∗ or Encupkr,tspub,tsspub1,T1∗. Now, the challenger ℬ randomly selects a tuple Kj,Vj from the H2-list and outputs K/eupkr,tspub,tsspub♭,P3m♭∗ as a guess of eP,Pabc. If A has ever inquired about one of H2ecH1T0∗,upkr+tspub+tsspub0 or H2ecH1T1∗,upkr+tspub+tsspub1, the H2-list has a probability of 1/2 that contains Kj,Vj, Kj=H2ecH1T♭∗,upkr+tspub+tsspub♭=H2eP,Pcu+s+x♭b+m♭∗. If ℬ takes this tuple Kj,Vj from the H2-list, then K/eupkr,tspub+tsspub♭,P3m♭∗=eP,Pabc.
The whole security simulation game is completed here. Next, we calculate the value ofϵ′ which is the lowest probability of ℬ correctly outputting eP,Pabc. It is easy to know that the premise that it can correctly output its guess value of eP,Pabc is that the game can continue to the guessing stage without terminating the game in the middle. Now, we analyze the possibility that ℬ does not terminate the game while the game is in progress. For this purpose, we first give the definition of the following events:E0: in the stage when the adversary A performs queries of the time trapdoor, the challenger ℬ does not terminate the simulation security gameE1: in the challenge stage, the challenger ℬ does not terminate the simulation security game
We first state that, as in [38], events E1 and E2 occur with a high enough probability. Next, we give the following three claims.Claim 1: in the stage when the adversary A performs queries of the time trapdoor, the probability that the challenger ℬ does not terminate the simulation security game is 1/e at least. Thus, PrE0≥1/e.Proof.
When the adversaryA queries for the time trapdoor of time points, for the sake of generality, we suppose that A does not query the same time trapdoor twice. A trapdoor (the user’s time trapdoor or the time server’s time trapdoor) query causes ℬ to terminate the simulation security game with a probability of 1/qT+1; therefore, a trapdoor query does not cause ℬ to terminate the game with a probability of 1−1/qT+1. In addition, since the maximum number of times A can query the time trapdoor is qT, the probability that the simulation security game will not be terminated after qT queries is 1−1/qT+1qT≥1/e at least.Claim 2: in the challenge stage, the probability that the challenger ℬ does not terminate the simulation security game is 1/qT at least. Thus, PrE1≥1/qT.Proof.
If the adversaryA can generate T0∗, T1∗ with the property n0∗=n1∗=1, then the challenger ℬ will terminate the simulation security game during the challenge stage. Since A has not queried for the trapdoor for T0∗, T1∗, we have that n0∗,n1∗ are independent of A. Therefore, Prn♭∗=0=1/qT+1 for ♭=0,1, and then we have that Prn0∗=n1∗=1=1−1/qT+12≤1−1/qT. Therefore, there is a probability of at least 1/qT that ℬ does not terminate the game.Since the adversaryA is not allowed to query the time trapdoor of the designated decryption time T0,T1 during the game, the events E0 and E1 are independent of each other, so we can get PrE0∩E1≥1/eqT.Assume that the adversaryA has acquired the public keys upkr=uP, tspub=sP, and tsspub=xP in the actual attack game. The adversary A selects a pair of designated decryption time points T0∗,T1∗ to be challenged. The challenger ℬ produces the challenge ciphertext C♭∗=P3,J as a response. Therefore, we have the following Claim 3.Claim 3: in the actual attack game, the adversary A has at least the probability of ϵ to perform an H2 query for one of H2ecH1T0∗,upkr+tspub+tsspub0, H2ecH1T1∗,upkr+tspub+tsspub1.Before giving the proof, we first give the definition of the following events:E2: in the actual attack game, A does not query either H2ecH1T0∗,upkr+tspub+tsspub0 or H2ecH1T1∗,upkr+tspub+tsspub1E3: in the guess stage, A outputs the guess ♭′ of ♭ satisfying ♭=♭′Proof.
WhenE2 occurs, it is obvious that the bit ♭∈0,1 indicates whether C♭∗ is the challenge ciphertext corresponding to the designated decryption time, which has nothing to do with A’s knowledge. Thus, the probability of PrE3 is 1/2 at most. In the real attack game, because A has the advantage of ϵ, we have PrE3−1/2≥ɛ and Pr¬E2≥2ɛ. Now, we give the specific argument for the truth of Pr¬E2≥2ɛ as follows:(7)PrE3=PrE3|E2PrE2+PrE3|¬E2Pr¬E2≤PrE3|E2PrE2+Pr¬E2≤12PrE2+Pr¬E2≤12+12Pr¬E2PrE3≥PrE3|E2PrE2≥12PrE2≥12−12Pr¬E2.From the above two formulas, we know thatϵ≤PrE3−1/2≤1/2Pr¬E2. Thus, we have Pr¬E2≥2ɛ in the actual attack game.If the challengerℬ does not terminate the game, it means that, in the process of simulating the actual attack game, the adversary A has queried one of H2ecH1T0∗,upkr+tspub+tsspub0, H2ecH1T1∗,upkr+tspub+tsspub1. Thus, Pr¬E2≥2ϵ.Claim 4: the probability that the challenger ℬ can solve the BDH problem successfully in the guess stage is ϵ/qH2.Proof.
Assuming the event of Claim 3 occurs, the value of one of the two cases ofecH1T♭∗,upkr+tspub+tsspub♭ will be stored in the H2-list. Consequently, in the guess stage, the challenger ℬ has at least the probability of 1/qH2 to select the correct pair from the H2-list. Therefore, on the premise that ℬ does not terminate the simulation game, the possibility that ℬ can successfully solve the BDH problem is ϵ/qH2.
According to Claims 1 and 2, during the simulation game, the probability that the challengerℬ will not terminate the game is at least 1/eqT. And according to Claim 4, if ℬ does not terminate the simulation security game, the probability that ℬ can successfully solve the BDH problem is ϵ/qH2. Therefore, through the security simulation game of the aforementioned adversary A and challenger ℬ, the possibility of successfully solving the BDH problem is ɛ/eqTqH2. Thus, Theorem 1 is proved.


## 4.3. Efficiency Analysis

We contrast between our SETRE scheme and two representative noninteractive time server TRE schemes: the classic BC-TRE scheme put forward by Blake and Chan [9] and the AnTRE scheme, which has highest efficiency up till now, put forward by Chalkias et al. [12].We letBP be a notation of the bilinear pairing operation, PAec and PMec be a notation of point addition and point multiplication operations in G1 separately. Let Expec be a notation of the exponentiation operation in G2 and Inv be a notation of the modular inverse operation in ℤq∗. Let H1 represent a hash function operation that maps binary strings of any length to an element in group G1, H2 represent the hash function operation that maps an element in group G2 to a string of log2q length 0 and 1, and H3 represent the hash function operation of mapping a binary string of any length to an element of ℤq∗. Based on the MIRACL large integer library, we program and implement the basic operations described above, in which the relevant parameters are set as follows: the elliptic curve is a supersingular elliptic curve E:y=x3+1 mod p on the finite field Fp (p is a 512-bit large prime number), and its prime order q is a 160-bit prime number; the bilinear map uses the Tate pairing algorithm to map the aforementioned discrete logarithm subgroup on the elliptic curve to the discrete logarithm subgroup on Fp2. The configuration of the running environment is as follows: Intel(R) Core(TM) i5-4210M @ 2.60 GHz microprocessors, 64 bit and 8 GB memory, Microsoft Visual Studio 2010. 987654321 is the seed that generates the associated random numbers. We take the calculation time of Expec as the basic unit so that the calculation results are not related to the specific computer performance. We then calculate and record the ratio of the calculation time of each related basic operation in these schemes to the calculation time of Expec, as shown in Table 1.Table 1
Calculation cost of related basic operations relative to theExpec operation.
Related basic operationsNotationRelative costBilinear pairingBP3.4457Point addition inG1PAec0.0072Point multiplication inG1PMec1Exponentiation inG2Expec0.3220Modular inverse inℤq∗Inv0.0030Hash function:0,1∗⟶G1H10.3368Hash function:G1⟶0,1log2qH20.0782Hash function:0,1∗⟶ℤq∗H30.0030In our SETRE scheme, the TS-Rel stage requires onePMec and one H1 to calculate ST=s+xH1T, and the total calculation cost of the TS-Rel stage is 1.003. The Enc stage requires one PMec for rP, two PAec for Spub, one H1, one PMec, and one BP for erH1T,Spub, and one H2 for H2K, and the total calculation cost of the Enc stage is 5.875. The Dec stage requires one H1, one PMec, one PAec, and one BP for K′=eU,ST+uH1T and one H2 for M⊕H2K, and the total calculation cost of the Dec stage is 4.868. We sum up the calculation cost of the schemes of BC-TRE, AnTRE, and our SETRE as shown in Table 2. It should be pointed out that the hash functions H1 and H2 in the scheme of AnTRE are approximately equivalent to H3 in Table 1, and the hash functions H3 and H4 in the scheme of AnTRE are approximately equivalent to H2 in Table 1.Table 2
Calculation cost of BC-TRE, AnTRE, and our SETRE.
SchemePhaseBC-TRE [9]AnTRE [12]Our SETRETS−RelPMec+H1=1.337PMec+Inv+H3=1.006PMec+H1=1.337Enc3BP+2PMec+H3=12.3404PMec+PAec+Expec+BP+2H2+2H3=7.9342PMec+2PAec+H1+BP+H2=5.875DecBP+Expec+H1+H2=4.183BP+PMec+2H2+H3=4.605H1+PMec+PAec+BP+H2=4.868Total17.8613.5512.08Table2 shows that our SETRE scheme has improved by 32.4% and 10.8%, respectively, compared with the schemes of BC-TRE and AnTRE. In addition, in the aspect of security, our SETRE scheme realizes one-time pad for the time trapdoor. Therefore, compared with the previous schemes, our SETRE greatly improves the security of the time server’s private key. In terms of storage, we need 160 bits of storage space for each private key of the time server and 1024 bits for each public key of the time server. Therefore, if it is assumed that the time server broadcasts a time trapdoor every half an hour and needs to store the session time server private key and public key for 10 years, then the additional storage space required by our scheme is 24∗2∗365∗10∗(1024 + 160)bit≈24.7 MB, which only adds almost negligible storage burden to the time server.


## 5. Generic Scheme of SETRE

We will attempt to propose a generic scheme of SETRE based on GPKE and call it generic SETRE, abbreviated as GSETRE.


### 5.1. Formal Definition

We now formalize the definition of our GSETRE scheme.Definition 7.
Our GSETRE scheme includes three entities which are time server, sender, and receiver and a polynomial-time randomized algorithm 6 tuplesEGSETRE=Setup,TS_KeyGen,User_KeyGen,Enc,Rel,Dec, whereSetup: generates a public parameter params from a security parameterTS_KeyGen: calculates and generates the fixed public/private key pair tspub,tspriv and the session public/private key pair tsspub,tsspriv of the time serverUser_KeyGen: calculates and generates the public/private key pair upk,usk of the system userEnc: inputs M,upk,T,tspub, and tsspub that correspond to the designated decryption time point T to the Enc algorithm of EGPKE and outputs the ciphertext CGSETRERel: given the private key tspriv of the time server, a designated decryption time point T, and its corresponding session private key tsspriv and produces a time server’s time trapdoor STDec: inputs ST and usk into the Dec algorithm of EGPKE and outputs plaintext M or ⊥


### 5.2. Construction

We construct aEGSETRE scheme by introducing ESETRE into EPKE. EGSETRE includes the following algorithm 6 tuples:Setup: this algorithm is consistent with theSetup algorithm of our concrete ESETRE schemeTS_KeyGen: this algorithm is consistent with theTS_KeyGen algorithm of our concrete ESETRE schemeUser_KeyGen: this algorithm is consistent with theUser_KeyGen algorithm of our concrete ESETRE schemeEnc: the sender usesupkr=uP of the receiver, tspub=sP of the time server, a designated decryption time point T∈0,1∗, and tsspub=xP corresponding to the designated decryption time point T∈0,1∗ to encrypt the plaintext M as the following operations:(1)
Usesupkr to encrypt the plaintext M and calculates EPKE’s ciphertext CGPKE=EncM,uP.(2)
Chooses a functionf⋅ randomly and calculates U=f⋅⋅P.(3)
UsesCGPKE, tspub, tsspub, and T to calculate(8)V=CGPKE⋅eH1T,f⋅⋅tspub+tsspub=CGPKE⋅eH1T,f⋅⋅s+xP.(4)
OutputsEGSETRE’s ciphertext CGSETRE=U,V=f⋅⋅P,EncM,uP⋅eH1T,f⋅⋅s+xP.Rel: this algorithm is consistent with theST_Rel algorithm of our concrete ESETRE schemeDec: the receiver uses the time trapdoorsST of the designated decryption time point T∈0,1∗ and the private key uskr=u of the receiver to decrypt the ciphertext CGSETRE=U,V as the following operations:(1)
CalculatesCGPKE′=V/eST,U(2)
CalculatesDecCGPKE′,u to recover the corresponding plaintext MSupposeCGSETRE is the valid ciphertext; then, we have U=f⋅⋅P and V=CGPKE⋅eH1T,f⋅⋅s+xP. We can verify the correctness of the decryption as described in the following:(9)CGPKE′=VeST,U=Ves+xH1T,f⋅⋅P=CGPKE⋅eH1T,f⋅⋅s+xPeH1T,f⋅⋅s+xP=CGPKEDecCGPKE′,u=DecCGPKE,u=M.


### 5.3. Security and Efficiency Analysis

From the perspective of security, since theEGSETRE scheme is obtained by introducing ESETRE into the EGPKE scheme, which is equivalent to encapsulating the EGPKE scheme’s ciphertext, the security of the EGPKE scheme will be enhanced after introducing ESETRE. Firstly, the decryption operation needs to decrypt the ESETRE’s ciphertext to get the ciphertext of the EGPKE scheme. However, the decryption of ESETRE requires a valid time trapdoor, and the attacker cannot construct the required time trapdoor without knowing the time server’s private key and session private key. Secondly, decrypting the EGPKE ciphertext requires the private key of the legitimate receiver.From the perspective of efficiency, compared with theEGPKE scheme, the EGSETRE scheme adds other additional operations in the encryption and decryption process, which inevitably leads to a decrease in efficiency. However, when using the idea of the general scheme to construct a concrete scheme, the parameters of the ESETRE scheme can be integrated into the same logical step of the EGPKE scheme as far as possible, so as to minimize the decline of efficiency. In addition, in terms of storage space, the time server only needs to add a small amount of storage space, as described in the above section.


## 5.1. Formal Definition

We now formalize the definition of our GSETRE scheme.Definition 7.
Our GSETRE scheme includes three entities which are time server, sender, and receiver and a polynomial-time randomized algorithm 6 tuplesEGSETRE=Setup,TS_KeyGen,User_KeyGen,Enc,Rel,Dec, whereSetup: generates a public parameter params from a security parameterTS_KeyGen: calculates and generates the fixed public/private key pair tspub,tspriv and the session public/private key pair tsspub,tsspriv of the time serverUser_KeyGen: calculates and generates the public/private key pair upk,usk of the system userEnc: inputs M,upk,T,tspub, and tsspub that correspond to the designated decryption time point T to the Enc algorithm of EGPKE and outputs the ciphertext CGSETRERel: given the private key tspriv of the time server, a designated decryption time point T, and its corresponding session private key tsspriv and produces a time server’s time trapdoor STDec: inputs ST and usk into the Dec algorithm of EGPKE and outputs plaintext M or ⊥


## 5.2. Construction

We construct aEGSETRE scheme by introducing ESETRE into EPKE. EGSETRE includes the following algorithm 6 tuples:Setup: this algorithm is consistent with theSetup algorithm of our concrete ESETRE schemeTS_KeyGen: this algorithm is consistent with theTS_KeyGen algorithm of our concrete ESETRE schemeUser_KeyGen: this algorithm is consistent with theUser_KeyGen algorithm of our concrete ESETRE schemeEnc: the sender usesupkr=uP of the receiver, tspub=sP of the time server, a designated decryption time point T∈0,1∗, and tsspub=xP corresponding to the designated decryption time point T∈0,1∗ to encrypt the plaintext M as the following operations:(1)
Usesupkr to encrypt the plaintext M and calculates EPKE’s ciphertext CGPKE=EncM,uP.(2)
Chooses a functionf⋅ randomly and calculates U=f⋅⋅P.(3)
UsesCGPKE, tspub, tsspub, and T to calculate(8)V=CGPKE⋅eH1T,f⋅⋅tspub+tsspub=CGPKE⋅eH1T,f⋅⋅s+xP.(4)
OutputsEGSETRE’s ciphertext CGSETRE=U,V=f⋅⋅P,EncM,uP⋅eH1T,f⋅⋅s+xP.Rel: this algorithm is consistent with theST_Rel algorithm of our concrete ESETRE schemeDec: the receiver uses the time trapdoorsST of the designated decryption time point T∈0,1∗ and the private key uskr=u of the receiver to decrypt the ciphertext CGSETRE=U,V as the following operations:(1)
CalculatesCGPKE′=V/eST,U(2)
CalculatesDecCGPKE′,u to recover the corresponding plaintext MSupposeCGSETRE is the valid ciphertext; then, we have U=f⋅⋅P and V=CGPKE⋅eH1T,f⋅⋅s+xP. We can verify the correctness of the decryption as described in the following:(9)CGPKE′=VeST,U=Ves+xH1T,f⋅⋅P=CGPKE⋅eH1T,f⋅⋅s+xPeH1T,f⋅⋅s+xP=CGPKEDecCGPKE′,u=DecCGPKE,u=M.


## 5.3. Security and Efficiency Analysis

From the perspective of security, since theEGSETRE scheme is obtained by introducing ESETRE into the EGPKE scheme, which is equivalent to encapsulating the EGPKE scheme’s ciphertext, the security of the EGPKE scheme will be enhanced after introducing ESETRE. Firstly, the decryption operation needs to decrypt the ESETRE’s ciphertext to get the ciphertext of the EGPKE scheme. However, the decryption of ESETRE requires a valid time trapdoor, and the attacker cannot construct the required time trapdoor without knowing the time server’s private key and session private key. Secondly, decrypting the EGPKE ciphertext requires the private key of the legitimate receiver.From the perspective of efficiency, compared with theEGPKE scheme, the EGSETRE scheme adds other additional operations in the encryption and decryption process, which inevitably leads to a decrease in efficiency. However, when using the idea of the general scheme to construct a concrete scheme, the parameters of the ESETRE scheme can be integrated into the same logical step of the EGPKE scheme as far as possible, so as to minimize the decline of efficiency. In addition, in terms of storage space, the time server only needs to add a small amount of storage space, as described in the above section.


## 6. Summary and Outlook

With the purpose of enhancing TRE security, a concrete SETRE scheme and a generic SETRE scheme based on the BDH assumption in the random oracle model are put forward. In our SETRE schemes, the time server uses a different session key to generate an “encryption-like” trapdoor at different time points. This operation uses the idea of one-time pad for the generation of each time trapdoor, which prevents the time trapdoor from being known in advance due to the leakage of the time server’s private key and thus prevents the ciphertext from being decrypted in advance.To ensure the anonymity of each system user identity to the time server, most current TRE solutions use broadcast to distribute time trapdoors. If time trapdoors are broadcast in a coarse-grained manner, many users may not have corresponding time trapdoors for the specified decryption time. In order to meet the time trapdoor specified by the user as far as possible, it is required to broadcast the time trapdoors with fine granularity, but this would waste communication resources. Therefore, designing a TRE that can support the specified arbitrary release time, anonymize the user identity, and prevent the time server from denial-of-service attacks will be a very practical and challenging task in the future. In addition, we will explore the combination of TRE with other cryptographic primitives, such as order-revealing encryption [39], so that more scenarios can have the function of controlling the decryption time.



---

*Source: 5593363-2021-05-27.xml*