Provably Secure Timed-Release Public Key Encryption

Provably Secure Timed-Release Public Key Encryption

JUNG HEE CHEON

Seoul National University,Korea

and

NICHOLAS HOPPER

YONGDAE KIM

IVAN OSIPKOV

University of Minnesota-Twin Cities

A timed-release cryptosystem allows a sender to encrypt a message so that only the intended recipient can read it,and only after a speci?ed time.We formalize the concept of a secure timed-release public-key cryptosystem and show that,if a third party is relied upon to guarantee decryption after the speci?ed date,this concept is equivalent to identity-based encryption;this explains the observation that all known constructions use identity-based encryption to achieve timed-release security.We then give several provably-secure constructions of timed-release en-cryption:a generic scheme based on any identity-based encryption scheme,and two more-e?cient schemes based on the existence of cryptographically admissible bilinear mappings.The?rst of these is essentially as e?cient as the Boneh-Franklin Identity-Based encryption scheme,and is provably secure and authenticated in the random oracle model;the?nal scheme is not authenti-cated but is provably secure in the standard model(i.e.,without random oracles).

Categories and Subject Descriptors:E.3[Data]:Data Encryption—Public Key Cryptosystems

General Terms:Security,Theory

Additional Key Words and Phrases:Timed-release,authenticated encryption,key-insulated en-cryption

1.INTRODUCTION

The goal of timed-release cryptography is to“send a message into the future.”One way to do this is to encrypt a message such that the receiver cannot decrypt the ciphertext until a speci?c time in the future.Such a primitive would have many practical applications;a few examples include preventing a dishonest auctioneer from prior opening of bids in a sealed-bid auction[Rivest et al.1996],prevent-ing early opening of votes in e-voting schemes,fair exchange,release of classi?ed information,and delayed veri?cation of a signed document,such as electronic lotter-ies[Syverson1998]and check cashing.The problem of timed-release cryptography was?rst mentioned by[May1993]and then discussed in detail by[Rivest et al. 1996].

Let us assume that Alice wants to send a message to Bob such that Bob will not be able to open it until a certain time.Previous solutions fall into two categories:—Time-lock puzzles:Alice encrypts her message so that Bob needs to perform non-parallelizable computation without stopping for the required time to decrypt it. If Alice accurately predicts Bob’s computing resources between now and the ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY,Pages1–0??.

2·

desired time,then Bob recovers the message.

—Trusted decryption agents:Alice encrypts a message such that Bob needs some secret value,published by a trusted agent on the required date,in order to decrypt the message.Once the agent releases the information,Bob can decrypt the message.

The?rst approach puts considerable computational overhead on the message re-ceiver,which makes it undesirable for real-life scenarios.In addition,knowing the computational complexity of decryption,while giving us a lower bound on the com-puting time Bob may need to decrypt the message,does not guarantee that the plaintext will be available at a certain date.Still,this approach is widely used for speci?c applications[Boneh and Naor2000;Bellare and Goldwasser1996;Syverson 1998;Garay and Pomerance2002;2003].The agent-based approach,on the other hand,relieves Bob from performing non-stop computation,sets the date of decryp-tion precisely and does not require Alice to have information on Bob’s capabilities. This comes at a price,though:the agents have to be trusted and they have to be available at the designated time.

In this paper we concentrate on schemes that use such“decryption agents.”We formalize this notion of a secure timed-release encryption scheme and show that it is equivalent to the notion of strongly key-insulated encryption[Dodis et al.2002]; when there is no a priori bound on the number of time periods,this notion is, in turn,known to be equivalent to identity-based encryption,or IBE[Bellare and Palacio2002].We also give several provably-secure constructions of timed-release public-key encryption,including the?rst provably-secure generic construction in the literature,and the?rst e?cient scheme that is provably secure in the standard model,that is,without random oracles.

Our results also cast new light on several previous schemes that appear in the literature:each can be seen as an adaptation of a known key-insulated encryption scheme.For example,[Rivest et al.1996]propose that the agent could encrypt messages on request with a secret key which will be published on a designated date by the agent,or the agent can precompute pairs of public/private keys,publish all public keys and release the private keys on the required days;these exactly?t known key-insulated schemes appearing in the literature.The scheme of[Crescenzo et al. 1999]essentially replaces publication of the key with publication of the message, requiring the receiver to engage in a conditional oblivious transfer protocol with the agent to decrypt the message.In[Chen et al.2002],the authors proposed to use Boneh and Franklin’s IBE scheme[Boneh and Franklin2003]for timed-release encryption:essentially,the scheme replaces the identity in an IBE scheme with the time of decryption.Similar proposals appear in[Marco Casassa Mont and Sadler 2003;Blake and Chan2005].

While some of the above proposals contain informal proofs of security,none of them consider and/or give a formal treatment of the security properties of timed-release public key encryption(or TR-PKE).The?rst formal treatments of TR-PKE security were displayed in[Cheon et al.2004]and then strengthened in[Cheon et al.2006].Independently,[Cathalo et al.2005]introduce another notion of timed-release security and argue that it is not implied by key-insulated encryption; however,this seems to be a side e?ect of an overly-restrictive model in which a user ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·3 must commit to a speci?c decryption agent before choosing his public key. Authentication for Timed-Release Encryption.Many of the applications of timed-release cryptography mentioned above require some form of authentication as well. For example,if there is no authentication of bids in a sealed-bid auction,any bidder may be able to forge bids for others,or force the auction to fail by submitting an unreasonably high bid.In this paper,we consider the security properties required by these applications and develop formal security conditions for a Timed-Release Public Key Authenticated Encryption(TR-PKAE)scheme.

One avenue for developing a TR-PKAE scheme would be composing an unauthen-ticated TR-PKE scheme with either a signature scheme or a(non-timed-release) PKAE scheme.Although such constructions are possible,we note that the details of this composition are not trivial;examples from[An2001;Dodis and Katz2005] illustrate that naive constructions can fail to provide the expected security prop-erties.Additionally,we note that such schemes are likely to su?er a performance penalty relative to a scheme based on a single primitive.Thus,besides introduc-ing a generic construction,we also introduce a provably secure construction of a TR-PKAE scheme that is essentially as e?cient as previous constructions of non-authenticated TR-PKE schemes[Chen et al.2002;Marco Casassa Mont and Sadler 2003;Blake and Chan2005].

2.DEFINITIONS

In this section we review security de?nitions that will be used in the paper.In addition,we introduce new de?nitions,namely,those of timed-release public key encryption(TR-PKE)and authenticated TR-PKE(TR-PKAE).

Identity Based Encryption.Formally,we de?ne a IBE scheme IBES to be a tuple of four randomized algorithms:

—Setup IBE(1k),which given input1k(the security parameter),produces public parametersπIBE,which include hash functions,message and ciphertext spaces among others.In addition,master secretδIBE is generated which is kept con?-dential by the central authority.

—Extract IBE(πIBE,δIBE,I),given public parametersπIBE,master secretδIBE and iden-tity I∈{0,1}?,outputs a secret key sk I.The I(together withπIBE)serves as the public key corresponding to identity I.

—Encrypt IBE(πIBE,I,m)computes the ciphertext c denoting the encryption for iden-tity I of message m with public parametersπIBE.

—Decrypt IBE(πIBE,sk I, c)outputs the plaintext corresponding to c if decryption is successful or the special symbol fail otherwise.

For consistency,we require that Decrypt IBE(πIBE,sk I,Encrypt IBE(πIBE,I,m))=m, for all valid(I,sk I),(πIBE,δIBE),and m.

We use the IND-ID-CCA notion of security for and IBE scheme[Boneh and Franklin2003].Brie?y,in this case,an adversary may adaptively ask for secret keys corresponding to arbitrary identities,and may also ask for decryption of any ciphertext using any identity.Eventually the adversary presents a“challenge iden-tity”and a pair of“challenge plaintexts”and is given the encryption of one of ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

4·

these plaintexts under the challenge identity.The adversary may then continue to ask for secret keys and decryptions,with the exception of the challenge identity or the challenge ciphertext.The adversary wins if it can correctly guess which of the challenge ciphertexts was encrypted by the challenger,and the scheme is secure if no polynomial time adversary wins with advantage non-negligibly greater than1

.

2 Public Key Encryption A public key encryption system PKE consists of three algo-rithms:

—KeyGen PKE,which on input1k,outputs public/private key pair(pk,sk).The public key includes also public parameters needed for encryption/decryption.—Encrypt PKE,which on input of pk and message m,outputs ciphertext c.—Decrypt PKE,which on input of ciphertext c and private key sk,outputs either some message m or failure symbol.

For consistency,it is required that Decrypt PKE(sk,Encrypt PKE(pk,m))=m,for all valid(pk,sk)and m.

We make use of a PKE that is IND-CCA secure against adaptive adversary as described in[Bellare et al.1998].Brie?y,the challenger generates a public/private key pair and gives the public key to the adversary.The adversary is allowed to query for the decryption of any ciphertext using the private key,produces a pair of challenge plaintexts and is given the encryption of one of the pair.The adversary wins if,given the ability to query the decryption of any message but the challenge ciphertext,it can correctly guess which of the two plaintexts was encrypted in the challenge step.

We note that given a secure IBES,we can easily obtain a secure PKE.For that purpose,each user simply runs IBES’s Setup IBE and Extract IBE,using an arbitrary identity I,to obtain its public key and private key(i.e.,the master secret key in IBES).The identity I along with IBES’s public parameters serves as user’s public key,while the master secret key serves as the private key.A straightforward ar-gument shows that if IBES is IND-ID-CCA secure then the corresponding PKE is IND-CCA2secure.However,since in practical applications we expect one to use more e?cient PKE constructions,we make use of separate IBES and PKE schemes in this paper.

Digital Signatures and Labels In addition to the above primitives,we will also use one-time signature schemes.We start with review of standard signatures?rst.A signature scheme DS consists of three algorithms:

—SigGen,which on input1k,outputs signing/veri?cation key pair(SK,V K).The V K includes also public parameters describing message space and so on.—Sig,which on input SK and message m,outputs signatureσ.

—Ver,which on input message m,signatureσand V K,outputs either true or false. For consistency,it is required that for every valid pair(SK,V K)and message m, Ver V K(m,Sig SK(m))=true.We will use the notion of strong unforgeability under adaptive chosen plaintext attacks(SUF-CMA).Brie?y,the challenger generates a ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·5 (SK,V K)pair and gives the V K to the adversary.The adversary is given signa-turesσ1,σ2,...,σq on adaptively chosen messages m1,m2,...,m q and outputs a pair(m,σ).The adversary wins if(m,σ)is a valid message signature pair and is not equal to any pair(m i,σi).

Beside standard signatures,we will also use one-time signatures which are de?ned analogously,except that in SUF-CMA the adversary is allowed to make only one query.One-time signatures are generally much more e?cient.

Besides using the above primitives,we also add public labels to IBE and PKE encryption/decryption mechanisms which are bound in a non-malleable way to the ciphertext[Shoup2004].In e?ect,ciphertext generation additionally takes as input a label,which becomes part of the ciphertext.When decrypting,one applies not only the decryption key but also the public label.The IND-ID-CCA and IND-CCA2 games can be modi?ed in a natural way to take labels into account.

2.1Timed-Release Public Key Encryption(TR-PKE)

In this section we formalize the functionality and security requirements for a timed-release public key encryption system.These requirements are meant to capture the implicit security requirements not addressed in previous work[May1993;Rivest et al.1996;Chen et al.2002;Marco Casassa Mont and Sadler2003;Blake and Chan2005];in particular they do not address the authentication requirements, which we add in f5736521192e45361066f55drmally,we can think of any principal in a TR-PKE system as?lling one or more of three roles.The timed-release agent–or TiPuS (TImed-release PUblic Server)–publishes a timed-release public key,and releases “tokens”that allow decryption of messages encrypted for the current time at regular intervals.The receiver publishes a public key that allows others to encrypt messages so that only he can decrypt them,using a secret key that he keeps private,and the appropriate timed-release token.The sender uses the receiver’s public key and the TiPuS public key to encrypt messages that can later be decrypted at the time of his choice.

2.1.1Functional requirements.Formally,we de?ne a timed-release public-key encryption systemΓto be a tuple of?ve randomized algorithms:

—Setup,which given input1k(the security parameter),produces public parameters πg,which include hash functions,message and ciphertext spaces among others.—TRSetup,which on inputπg,produces a pair(δ,πtr)whereδis a master secret andπtr the corresponding timed-release public parameters.This setup is carried out by TiPuS which keeps the master secret key con?dential,while all other parameters are public.We denote the combined public parameters ofπg andπtr byπ.

—KeyGen,given public parametersπg,outputs a pair of secret key and public key (sk,pk).

—TG(π,δ,T)computes the token tkn T corresponding to time T using(δ,π).This functionality is performed by TiPuS which publishes tkn T at time T.—Encrypt(π,pk,m,T)computes the timed-release ciphertext c denoting the encryp-tion of message m using public key pk,public parametersπand time encoding T.

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

6·

Algorithm2.1:Exp IND-CCA2

A,Γ

(k)

πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(pk,sk)←KeyGen(πg)

(m0,m1,T?)←A Decrypt(π,sk,·,·)(π,δ,pk)β←R{0,1}

c?←Encrypt(π,pk,mβ,T?)

β′←A Decrypt(π,sk,·,·)(π,δ,pk,c?)

if(A queried Decrypt(π,sk,c?,tkn T?)) then return(false)

else return(β′=β)Algorithm2.2:Exp IND-RTR-CCA2

A,Γ

(k)πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(m0,m1,pk?,T?)

←A TG(π,δ,·),Decrypt?(π,δ,·,·,·)(π)

β←R{0,1}

c?←Encrypt(π,pk?,mβ,T?)

β′←A TG(π,δ,·),Decrypt?(π,δ,·,·,·)(π,c?) if(A queried Decrypt?(π,sk?,c?,T?), where sk?corresponds to pk?,

or A queried TG(π,δ,T?))

then return(false)

else return(β′=β)

Adv IND-CCA2

A,Γ(k)=Pr[Exp IND-CCA2

A,Γ

(k)=true]?1

2

Adv IND-RTR-CCA2 A,Γ(k)=Pr[Exp IND-RTR-CCA2

A,Γ

(k)=true]?1

2

Fig.1.TR-PKE security experiments for the IND-CCA2and IND-RTR-CCA2games —Decrypt(π,sk, c,tkn T)outputs the plaintext corresponding to c if decryption is successful or the special symbol fail otherwise.

For consistency,we require that Decrypt(π,sk,Encrypt(π,pk,m,T),TG(π,δ,T))= m,for all valid(pk,sk),(π,δ),T,and m.Unlike the functional requirements speci?ed in[Cathalo et al.2005],we explicitly separate the functions TRSetup and KeyGen,allowing a user to generate keys independent of any timed-release server. This allows the sender to choose which servers to trust during encryption.

2.1.2Security.It is standard to require that the PKE cryptosystem be secure against adaptive chosen-ciphertext(IND-CCA2)attack[Racko?and Simon1991; Bellare et al.1998;An2001].Ideally,in a TR-PKE,the timed-release agent should not be able to read messages intended for third-party recipients.To that e?ect, we require that IND-CCA2security against a third party is provided even when the master secret is given to the adversary.We model this attack by a slightly modi?ed IND-CCA2game,shown in Figure1.Here,in addition to adaptively choosing two“challenge plaintexts”that the adversary will need to distinguish between, he also adaptively chooses a“challenge time”for which his challenge ciphertext will be decrypted;he wins when he can tell whether his challenge ciphertext is an encryption of his?rst or second plaintext for the challenge time,given access to a decryption oracle and the master secret key of the TiPuS.

The timed-release functionality is provided by the token-generating infrastructure (i.e.,TiPuS).Not knowing the corresponding token is what keeps the receiver from decrypting ciphertext until a designated time.To e?ect secure timed-release,any TR-PKE cryptosystem must provide con?dentiality against the receiver itself until the corresponding token is made available.We model this property by the IND-RTR-CCA2game,shown in Figure1;in this game,we modify the basic IND-CCA2game by allowing the adversary to adaptively choose the receiver’s public key pk?and time T?for the challenge.Instead of access to the timed-release secret,the adversary is given access to arbitrary tokens tkn T,where T=T?,and a decryption oracle ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·7 Decrypt?(π,δ,·,·,·)which computes Decrypt(π,·,·,TG(π,δ,·)).The adversary may thus compute the decryption of any ciphertext for any time,except the challenge ciphertext in the challenge time T?with chosen public key pk?.We say a timed-release public-key cryptosystemΓis secure if every polynomial time adversary A

has negligible advantages Adv IND-CCA2

A,Γ(k)and Adv IND-RTR-CCA2

A,Γ

(k).

2.2Strongly Key-Insulated Public Encryption

Key-insulated public key encryption was introduced by[Dodis et al.2002;2003; Bellare and Palacio2002]to address the problem of computer intrusion.The key idea is to break up the lifetime of a public key into periods,and split the decryption key between the user(say,a mobile device)and a trusted“helper”(say,a desktop server)to satisfy the following properties:

—(Sequential Key Updates)At the beginning of each time period,the helper se-curely transmits a“helper secret key”hsk i to the user,which he combines with his previous key,usk i?1,to obtain a secret key usk i that will decrypt messages encrypted during time period i.

—(Random Access Key Updates)Given any usk i and hsk j,the user can compute usk j.This is useful for error recovery and it also allows the user to decrypt old messages.

—(User Compromise)An adversary who is given access to(usk i,hsk i)for several time periods i cannot break the encryption for a new time period.

—(Helper Compromise)An adversary given only hsk cannot break the encryption scheme.

Combining the results of[Bellare and Palacio2002]and[Dodis and Katz2005] one obtains that the existence of secure SKIE-OTRU is a necessary and su?cient condition for the existence of secure IBE.Brie?y,a SKIE-OTRU scheme consists of the following algorithms:KG,which generates a triple(pk,usk0,hsk)of public key, initial user secret key,and master helper key;HKU,which computes a stage i helper secret key hsk i given(pk,hsk,i);UKU,which computes the stage i user secret key usk i given i,pk,hsk i,usk i?1;RUKU,which computes the stage i user secret key usk i given i,j,pk,hsk i,usk j,?i≥1,j≥0;Enc,which produces a ciphertext corresponding to m to be decrypted in stage i,given(pk,m,i);and Dec,which, given(i,pk,usk i,c)attempts to decrypt a ciphertext for stage i.Intuitively,hsk is given to a“helper”,who will securely transmit,at the beginning of each stage i,the secret hsk i to the user.The user can then compute usk i,delete any old usk’s in his possession,and use usk i to decrypt messages sent to him during stage i.The RUKU algorithm facilitates error recovery and allows for decryption of old ciphertexts.

A SKIE(and SKIE-OTRU)scheme is considered CCA-secure with optimal thresh-old if two conditions hold:(1)(IND-KIE-CCA2)given access to pk,a decryption oracle,and pairs(hsk i,usk i)of his choosing,an adversary cannot break the IND-CCA2of encryption scheme for a stage j for which he has not been given hsk j; and(2)(IND-S-CCA2)given pk,hsk,and a decryption oracle,an adversary cannot break the IND-CCA2of encryption scheme for any stage[Dodis et al.2002;2003; Bellare and Palacio2002].The idea of separation of the timed-release master and ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

8·

user secrets in a TR-PKE very closely parallels the notions of helper and user secrets in a key-insulated cryptosystem;and both involve a“time period”parameter for encryption and decryption.Furthermore,the two security conditions for a SKIE scheme,in which either user keys or helper keys are assumed to be compromised, closely resemble the TR-PKE conditions IND-CCA2and IND-RTR-CCA2developed here.

2.3Authenticated TR-PKE(TR-PKAE)

The notion of authenticated encryption has been explored in depth in[An2001; Abdalla et al.2001].In this section we adapt these de?nitions to give formal security and functionality requirements for a TR-PKAE scheme.

2.3.1Basic Cryptosystem.The syntactic de?nition of a TR-PKAE scheme is essentially the same as that of a TR-PKE scheme with the addition of the sender’s public and secret f5736521192e45361066f55dly,the types of Setup,TRSetup,KeyGen and TG stay the same,but Encrypt and Decrypt are modi?ed to take into account sender’s keys:—Encrypt(π,sk a,pk b,m,T)returns an authenticated timed-release ciphertext c de-noting the encryption from sender A to receiver B of m for time T.—Decrypt(π,pk a,sk b, c,tkn T)outputs plaintext m if both decryption and authen-tication are successful and the special symbol fail otherwise.

The consistency requirement is modi?ed to require that,for all valid(pk a,sk a), (pk b,sk b),(π,δ),T,and m,Decrypt(π,pk a,sk b,Encrypt(π,sk a,pk b,m,T),TG(π,δ,T))=m.

2.3.2Security.

Con?dentiality.The con?dentiality requirements of a TR-PKAE are essentially the same as the con?dentiality requirements of a TR-PKE;except that we make the conservative assumption that the third party(in the case of IND-CCA2)or the receiver(in the case of IND-RTR-CCA2)has compromised the sender’s secret key. This results in two new notions,IND-KC-CCA2and IND-RTR-KC-CCA2,which we de?ne formally in Figure2.As before,we say that a TR-PKAE scheme provides con-?dentiality if every polynomial time adversary has negligible advantage,as de?ned in Figure2.

As in the case of TR-PKE,the di?erence between IND-KC-CCA2and IND-RTR-KC-CCA2is in reversal of adversary roles.In IND-RTR-KC-CCA2,the goal is to ensure security against the receiver itself prior to the designated time. Ciphertext(Plaintext)Forgery.For authentication properties of TR-PKAE, we concentrate on ciphertext forgery(plaintext forgery is de?ned analogously).We consider two types of ciphertext forgery:third-party forgery(TUF-CTXT),by an adversary that does not know the sender’s and receiver’s private keys but knows the master secret;and forgery by the ciphertext receiver(RUF-CTXT)[An2001]. If the TR-PKAE is not secure against TUF-CTXT then the scheme cannot claim authentication properties since a third party may be able to forge new(perhaps de-crypting to junk)ciphertexts between two users.If a TR-PKAE is not secure against RUF-CTXT,then the scheme does not provide non-repudiation1and furthermore,if 1Since the receiver can generate the ciphertext allegedly coming from another user to himself,the ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·9

Algorithm2.3:Exp IND-KC-CCA2

A,Γ

(k)πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(pk a,sk a)←KeyGen(πg)

(pk b,sk b)←KeyGen(πg)

κ←(π,δ,pk a,sk a,pk b)

(m0,m1,T?)

←A Decrypt(π,pk a,sk b,·,·)( κ)

β←R{0,1}

c?←Encrypt(π,sk a,pk b,mβ,T?)β′←A Decrypt(π,pk a,sk b,·,·)( κ,c?)

if(A queried

Decrypt(π,pk a,sk b,c?,tkn T?)) then return(false)

else return(β′=β)Algorithm2.4:Exp IND-RTR-KC-CCA2

A,Γ

(k)

πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(pk a,sk a)←KeyGen(πg)

κ←(π,pk a,sk a)

(m0,m1,pk?

b

,T?)

←A TG(π,δ,·),Decrypt?(π,δ,pk a,·,·,·)( κ)

β←R{0,1}

c?←Encrypt(π,sk a,pk?

b

,m b,T?)

β′←A TG(π,δ,·),Decrypt?(π,δ,pk a,·,·,·)( κ,c?)

if(A queried Decrypt?(π,pk a,sk?

b

,c?,T?) or TG(π,δ,T?))

then return(false)

else return(β′=β)

Adv IND-KC-CCA2

A,Γ(k)=Pr[Exp IND-KC-CCA2

A,Γ

(k)=true]?1

2

Adv KC-RTR-KC-CCA2 A,Γ(k)=Pr[Exp IND-RTR-KC-CCA2

A,Γ

(k)=true]?1

2

Fig.2.TR-PKAE experiments for the IND-KC-CCA2and IND-RTR-KC-CCA2games

the receiver’s private key is compromised,the attacker can impersonate any sender to this receiver.We introduce the following games to model unforgeability(see Figure3).

Receiver Unforgeability(RUF-CTXT and RUF-TR-CTXT).We introduce two notions of receiver unforgeability:RUF-CTXT in which the receiver cannot forge ciphertext to himself for any time and weaker timed-release notion of RUF-CTXT,called RUF-TR-CTXT,which requires that the receiver should not be able to forge ciphertext to himself for a future date.The notion RUF-TR-CTXT has two important impli-cations:(1)the receiver should discard any ciphertexts received past decryption dates if his private key may be compromised;and(2)the receiver may be able to prove to a third party that a ciphertext was generated by the alleged sender if he can produce a proof of ciphertext existence prior to the decryption date.The game in Figure3is an enhancement of the RUF-CTXT condition proposed by An[An 2001]to allow adaptive adversarial behavior:the receiver is not given access to the token for a single,adaptively-chosen challenge time period;in addition,the ad-versary can choose any receiver public key in the encryption queries.We say that a TR-PKAE encryption is secure against RUF-TR-CTXT,if every polynomial-time

adversary A has negligible advantage,Adv RUF-TR-CTXT

A,Γ(k),against the challenger in

the RUF-TR-CTXT game.The game for RUF-CTXT is a natural simpli?cation of RUF-TR-CTXT in which the receiver obtains the master secret(and thus the token queries are no longer required).

Third-Party Unforgeability(TUF-CTXT).In addition to timed-release receiver un-forgeability,we also require a time-independent third-party unforgeability(TUF-CTXT)condition,which allows to separate timed-release functionality from PKAE. Thus,in the TUF-CTXT game de?ned in Figure3,the master key is given to the receiver will not be able to prove to anybody that ciphertext was generated by the alleged sender even if all secret information is disclosed.

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

10·

Algorithm2.5:Exp TUF-CTXT

A,Γ

(k)

πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(pk a,sk a)←KeyGen(πg)

(pk b,sk b)←KeyGen(πg)

(c?,T?)

←A Encrypt?(π,sk a,pk b,·,·)(π,δ,pk a,pk b) if(Decrypt?(π,δ,pk a,sk b,c?,T?)=fail or

Encrypt?(π,sk a,pk b,·,T?)returned c?)

then return(false)

else return(true)Algorithm2.6:Exp RUF-TR-CTXT

A,Γ

(k)

πg←Setup(1k)

(δ,πtr)←TRSetup(1k)

(pk a,sk a)←KeyGen(πg)

(c?,T?,pk?

b

,sk?

b

)

←A TG(π,δ,·),Encrypt?(π,sk a,·,·,·)(π,pk a)

if(Decrypt?(π,δ,pk a,sk?

b

,c?,T?)=fail

or Encrypt?(π,sk a,pk?

b

,·,T?)returned c?

or(pk?

b

,sk?

b

)∈[KeyGen(1k)]

or A queried TG(T?))

then return(false)

else return(true)

Adv TUF-CTXT

A,Γ(k)=Pr[Exp TUF-CTXT

A,Γ

(k)=true].

Adv RUF-TR-CTXT

A,Γ(k)=Pr[Exp RUF-TR-CTXT

A,Γ

(k)=true.

Fig.3.TR-PKAE security experiments for the TUF-CTXT and RUF-TR-CTXT games adversary.We say that a TR-PKAE schemeΓis secure against TUF-CTXT if every

polynomial time adversary A has negligible advantage,Adv TUF-CTXT

A,Γ

(k),in k.

3.STRONGLY KEY-INSULATED PUBLIC ENCRYPTION AND TIMED-RELEASE Despite similarities between SKIE-OTRU and TR-PKE notions mentioned before, there is a key di?erence between them.In the SKIE-OTRU setting,a helper is associated with at most one user,and cooperates exclusively with that user,whereas in the TR-PKE setting,it is assumed that many users may use the services of the TiPuS server,but the interaction between each user and the server will be minimal. This results in several operational di?erences:1)User and Master Key Generation –in a TR-PKE scheme,they are generated independently,whereas in a SKIE-OTRU they are generated jointly;2)Dissemination of secrets per time period–a SKIE scheme must use a secure channel to send the hsk i to only one user,whereas the tokens generated by a TiPuS are assumed to be publicly disseminated;3)Security notion of“user compromise”–a SKIE scheme’s notion of“user compromise”is limited to chosen time periods and the keys are generated by the victim,whereas in TR-PKE’s notion the attacker is the user herself and she can generate her public key adaptively(perhaps without necessarily knowing the corresponding secret key) in order to break timed-release con?dentiality.The following theorem shows that despite these di?erences,these notions are essentially equivalent.

Theorem3.0.1.There exists a(chosen-ciphertext)secure timed-release public key encryption scheme if and only if there exists a secure strongly key-insulated public-key encryption scheme with optimal threshold that allows random-access key updates.

More precisely,given a SKIE-OTRU,PKE2and one-time signature DS one,we can construct a TR-PKE with the following properties:

—given an IND-CCA2adversary A against TR-PKE,we can construct algorithms B1 2The PKE can be constructed from the SKIE-OTRU.

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·11

and B2with run-time O(T ime(A))such that Adv IND-CCA2

A,TR?PKE (k)≤1

2

Adv SUF-CMA

B1,DS one

(k)+

Adv IND-CCA2

B2,PKE

(k).

—given an IND-RTR-CCA2adversary A against TR-PKE,we can construct algo-

rithms B1and B2with run-time O(T ime(A))such that Adv IND-RTR-CCA2

A,TR?PKE

(k)≤

1 2Adv SUF-CMA

B1,DS one

(k)+Adv IND-KIE-CCA2

B2,SKIE?OTRU

(k).

Conversely,given a TR-PKE scheme,we can construct a SKIE-OTRU with the

following properties:

—given an IND-S-CCA2adversary A against SKIE-OTRU,we can construct an algorithm B with run-time O(T ime(A))such that Adv IND-S-CCA2

A,SKIE?OTRU

(k)≤

Adv IND-CCA2

B,TR?PKE

(k).

—given an IND-KIE-CCA2adversary A against SKIE-OTRU,we can construct an

algorithm B with run-time O(T ime(A))such that Adv IND-KIE-CCA2

A,SKIE?OTRU

(k)≤

Adv IND-RTR-CCA2

B,TR?PKE

(k).

Proof.(Sketch)Suppose we have a secure TR-PKE schemeΓ=(Setup,TRSetup, TG,Encrypt,Decrypt).We construct a SKIE-OTRU scheme fromΓas follows.Set KG(1k)=((π,pk),sk,δ),where(π,δ)←TRSetup(1k)and(pk,sk)←KeyGen(π); HKU((π,pk),δ,i)=tkn i,where tkn i←TG(π,δ,i);UKU(i,(π,pk),tkn i,(sk,tkn i?1)) =(sk,tkn i);RUKU(i,j,(π,pk),tkn i,(sk,tkn j))=(sk,tkn i);Enc((π,pk),m,i)=c, where c←Encrypt(π,pk,m,i);and set Dec(i,(π,pk),(sk,tkn i),c)=

Decrypt(π,sk,c,tkn i).This scheme essentially makes the TiPuS server in TR-PKE schemeΓinto a helper for an SKIE-OTRU scheme.

It is easy to see that this scheme must be a secure SKIE-OTRU scheme.Suppose

an IND-S-CCA2attacker given access to spk=(π,pk),hsk=δand a decryption oracle can break the scheme;then it is easy to see that such an adversary can also

be used to mount an IND-CCA2attack onΓ,since these are exactly the resources given to an adversary in the IND-CCA2game.Likewise,an IND-KIE-CCA2adversary who can break the scheme given access to spk=(π,pk),selected(usk i,hsk i)= (sk,tkn i)pairs,and a decryption oracle can easily be used to mount an IND-RTR-CCA2attack onΓ:when the SKIE adversary makes a corruption request for stage

i,the corresponding RTR-CCA2adversary queries its TG oracle for tkn i and can forward(sk,tkn i)to the SKIE adversary since the RTR-CCA2adversary gets sk

as an input;all other queries made by the SKIE adversary can be passed directly

to the corresponding oracles of the RTR-CCA2adversary.The security reduction statements follow trivially.

Now suppose we have a secure SKIE-OTRU schemeΣ.IfΣhas the additional property that KG can be implemented as two independent keying algorithms that generate(pk h,hsk)and(pk u,usk),then it is straightforward to transformΣinto

a TR-PKE scheme.Since we would not expect this property to hold in general,we work around this problem as follows.We know that by the existence ofΣthere also exists an ordinary chosen-ciphertext secure PKCΠ=(PKGen,PKEnc,PKDec).

The idea behind our construction is that TRSetup will sample(spk,hsk,usk0)←Σ.KG(1k)and setπ=spk andδ=(hsk,usk0);KeyGen will sample(pk,sk)←Π.PKGen(1k)and output(pk,sk).TG(π,δ,i)will?rst compute hsk i=HKU(spk,hsk,i) and then use usk0and hsk i to compute tkn i=usk i=RUKU(i,0,spk,usk0,hsk i).

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

12·

Encryption and Decryption will use the multiple-encryption technique of[Dodis and Katz2005]with one-time signature scheme DS one.3Applying the results of [Dodis and Katz2005],an IND-CCA2attack on this scheme reduces to an IND-CCA2attack onΠ,while an IND-RTR-CCA2attack(even when receiver chooses its public key adaptively)on this scheme reduces to an IND-KIE-CCA2attack onΣ. 4.GENERIC CONSTRUCTIONS OF TR-PKE AND TR-PKAE

We note that the previous theorem essentially gives a generic construction of TR-PKE based on a SKIE-OTRU scheme.Note that since,as mentioned previously, SKIE-OTRU and IBE have been shown to be equivalent,this gives a generic con-struction using any IBE scheme as well.Here we elaborate on this construction and show how to turn it into TR-PKAE.

The main idea of the generic TR-PKE construction is to combine a PKE scheme4 and IBE using multiple encryption.Note that naive multiple encryption fails to provide adaptive chosen-ciphertext security as was shown in[Dodis and Katz2005]. More speci?cally,suppose that messages are encrypted?rst for the receiver and then for the time.Then the time server,in the IND-CCA2game,can win by removing the outer layer of encryption on the challenge ciphertext,re-encrypting for another time,and querying the decryption of this ciphertext.Similarly,if messages are ?rst encrypted for the time and then for the receiver,the receiver can win in the IND-RTR-CCA2game with a similar strategy.

Thus we need to be careful when combining encryptions and will use the approach to IND-CCA2multiple encryption proposed by Dodis and Katz[Dodis and Katz 2005].As in the proof of Theorem3.0.1,the resulting encryption scheme will be secure against IND-CCA2and IND-RTR-CCA2attacks.One can extend the TR-PKE gen to obtain TR-PKAE gen.For that purpose,one can use the Encrypt-then-Sign approach[An2001],where the TR-PKE gen ciphertext is signed by the sender using SUF-CMA secure digital signature scheme DS.

Due to similarity of TR-PKE gen and TR-PKAE gen constructions,below we im-mediately jump to the TR-PKAE gen construction.We obtain the corresponding TR-PKE gen by removing sender’s signature from the TR-PKAE gen mechanism.

4.1TR-PKAE gen:Generic TR-PKAE

The generic construction is shown in Figure4.The approach is to use IBE for construction of timed-release encryption(TRE)and then encrypt the message using multiple encryption that combines TRE and PKE,which results in non-authenticated version.To obtain TR-PKAE,we remark that requiring the sender to simply sign the ciphertext will not produce an IND-KC-CCA2or IND-RTR-KC-CCA2secure scheme since in these games the adversary has access to the sender’s secret key and thus may be able to generate a new signature on the challenge ci-phertext and submit this modi?ed challenge ciphertext to the decryption oracle–

3Speci?cally,to encrypt message m for time T,we:(1)pick s1←U

|m|,and set s2=m⊕s1,(2)

pick signing and veri?cation keys(SK,V K)for the one-time signature scheme DS one,(3)let c1=Σ.Enc V K(spk,s1,T),c2=Π.PKEnc V K(pk,s2),and(4)output(V K,c1,c2,Sig(V K,(T,c1,c2))). Decryption follows the scheme of[Dodis and Katz2005],except that c1is decrypted using tkn T= usk T.

4which may or may not be derived from the IBE scheme used

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·13 Setup/TRSetup:Given security parameter1k IBE for IBE,we run Setup IBE producing public parametersπIBE and master secretδIBE which is kept secret by the TiPuS.

KeyGen:Each user u?rst runs KeyGen PKE on input of security parameter1k chosen by u to obtain public/private key pair(pk PKE,sk PKE),and then runs SigGen DS with(another) input1k to obtain the signing/veri?cation key pair(SK DS,V K DS).The public key u in TR-PKAE is pk=(pk PKE,V K DS)and the private one is sk=(sk PKE,SK DS).

During PKE operations,the pk PKE and sk PKE will be used,while during DS operations the SK DS and V K DS are used.

TG:On input the time encoding T,the central server TiPuS outputs secret key sk T corresponding to identity T under the IBE.

Encrypt:Given the public key pk b of receiver and secret key sk a of the sender,mes-sage m and time encoding T,1)pick a random string s1of the same size as m and set s2=m⊕s1.2)Then pick signing and veri?cation key pair(SK,V K)

for one-time signature DS one.3)Compute c1=Encrypt V K

IBE (πIBE,T,s1)using la-

bel V K,compute c2=Encrypt V K

PKE (pk b,s2)using label V K.4)Compute sender’s

signature c3=Sig sk

a (T,c1,c2,V K,pk b).4)The resulting ciphertext is c=

(V K,T,c1,c2,c3,Sig SK(T,c1,c2,c3)).

Decrypt:Given ciphertext c=(V K,T,c1,c2,c3,Sig SK(T,c1,c2,c3))encrypted using pk b,sk a and time T,one decrypts it as follows:1)Verify one-time signature Sig SK(T,c1,c2,c3)using V K;2)Verify signature of the sender c3using pk a;3)

obtain tkn T=sk T;4)b s1=Decrypt V K

IBE (πIBE,sk T,c1);5)b s2=Decrypt V K

PKE

(sk b,c2),

6)construct b m=b s1⊕b s2.If any of the steps fail,output fail.

Fig.4.The TR-PKAE gen scheme

in the end,the adversary is able to decrypt the challenge ciphertext.To deal with this slight complication,prior to generation of the one-time signature,the sender signs the concatenation of the intermediate ciphertext,the one-time veri?cation key and the receiver’s public key.The one-time signature is then computed on the intermediate ciphertext and the sender’s signature–this ensures that the adversary will need to compute another one-time signature with the same veri?cation key in the previous attack.

Theorem4.1.1.The generic TR-PKAE gen scheme is secure against IND-KC-CCA2,IND-RTR-KC-CCA2,TUF-CTXT and RUF-CTXT provided that the one-time signature scheme is SUF-CMA secure,PKE is IND-CCA2secure,IBE is IND-ID-CCA secure and DS is SUF-CMA secure.

More precisely,given an IBE,PKE5,signature mechanism DS and one-time signature DS one,we can construct a TR-PKAE with the following properties:—given an IND-KC-CCA2adversary A against TR-PKAE,we can construct algo-rithms B1and B2with run-time O(T ime(A))such that Adv IND-KC-CCA2

A,TR?PKAE

(k)≤

1 2Adv SUF-CMA

B1,DS one

(k)+Adv IND-CCA2

B2,PKE

(k).

—given an IND-RTR-KC-CCA2adversary A against TR-PKAE,we can construct al-gorithms B1and B2with run-time O(T ime(A))such that Adv IND-RTR-KC-CCA2

A,TR?PKAE

(k)≤

1 2Adv SUF-CMA

B1,DS one

(k)+Adv IND-ID-CCA

B2,IBE

(k).

—given an RUF-CTXT adversary A against TR-PKAE,we can construct algo-rithms B1and B2with run-time O(T ime(A))such that Adv RUF-CTXT

A,TR?PKAE

(k)≤5The PKE can be constructed from the IBE.

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

14·

Adv SUF-CMA

B1,DS one (k)+Adv SUF-CMA

B2,DS

(k).

—given an TUF-CTXT adversary A against TR-PKAE,we can construct algo-rithms B1and B2with run-time O(T ime(A))such that Adv TUF-CTXT

A,TR?PKAE

(k)≤

Adv SUF-CMA

B1,DS one (k)+Adv SUF-CMA

B2,DS

(k).

Proof.First,note that in the IND-KC-CCA2and IND-RTR-KC-CCA2games,we can assume that the signing/veri?cation key pair in the challenge is di?erent from those used in Decryption queries,for otherwise we can easily break the SUF-CMA guarantee of the one-time signature.

To show that the scheme is secure against IND-KC-CCA2,whenever adversary A makes a decryption query,we decrypt s1using the master secret(after having veri?ed the signatures)and forward c2for decryption to PKE oracle.During the challenge phase,we pick s1at random,compute c1and submit s2,1=m1⊕s1 and s2,2=m2⊕s1along with V K as the challenge parameters to PKE challenger which encrypts one of s2,i.We return the resulting complete ciphertext(with all required signatures)to A.Now suppose that the adversary submits a ciphertext (di?erent from the challenge one)for decryption after the challenge.If the V K in the submitted ciphertext is the same as in the challenge,then either the adversary submits the challenge ciphertext(which is an invalid query)or he breaks SUF-CMA of the one-time signature scheme(in which case we return a random bit to PKE challenger).Otherwise,since V K is di?erent from the challenge one,we can use the PKE decryption oracle without being forced to submit the challenge ciphertext that was returned by PKE challenger.If A can guess which message was encrypted,then we automatically guess which message was encrypted by PKE during the challenge thus breaking IND-CCA2security of PKE.Noting that,in case of SUF-CMA break, we win against the PKE with probabilty1/2,the stated reductions follow.

To show that the scheme is secure against IND-RTR-KC-CCA2,note that1)the token queries correspond to Extract queries in underlying IBE,and2)for decryp-tion queries we can use(to decrypt s1)the IBE decryption oracle(where s2can be decrypted using the private key provided by the adversary).Also,during the challenge,we submit corresponding challenge to IBE similarly to the IND-KC-CCA2 approach.Once again,if after the challenge the(valid)decryption query submitted by the adversary has the same V K as in the challenge,then we break the SUF-CMA of the one-time signature(in which case we return a random bit).Otherwise,we can use the IBE decryption oracle even after the challenge.If adversary manages to guess correctly which message was encrypted in the challenge,we automatically guess which message was encrypted by the IBE challenger,thus breaking IND-ID-CCA security of IBE.Reduction analysis stays the same as in the previous case. Since RUF-CTXT security automatically implies TUF-CTXT[An2001],we need ?nally to prove RUF-CTXT security,where the adversary knows the timed-release secret but no longer knows the sender’s secret key.The adversary has access to encryption oracle where he can submit any m,T and pk b.In the end,he returns the secret receiver key sk?b,time T?and ciphertext c?which should contain the sender’s authentication.If the adversary manages to generate a new sender’s signature in the returned ciphertext(either with the new input or a di?erent signature with one of the inputs used during encryption queries),then we break the SUF-CMA security of the DS.Otherwise,the V K?,T?,c?1,c?2,c?3and pk?b in the returned ciphertext ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·15 should be the same as in one of the ciphertexts returned by the encryption oracle. Thus,if the returned ciphertext is di?erent from the ones returned by the encryption oracle,the adversary has to break SUF-CMA of the one-time signature in order to win.The stated reductions follow easily.

4.2TR-PKE gen:Generic TR-PKE

To obtain generic TR-PKE gen,we can simply remove the parts in the TR-PKAE gen description where the sender signs with his secret key,i.e.we remove c3from the construction while leaving everything else intact.The proofs and the reductions stay the same as in TR-PKAE gen.

Theorem4.2.1.The generic TR-PKE gen construction is secure against IND-CCA2and IND-RTR-CCA2attacker provided that the IBE is IND-ID-CCA secure, PKE is IND-CCA2secure and the underlying one-time signature is SUF-CMA secure.

5.TR-PKAE BM:TR-PKAE BASED ON A SINGLE PRIMITIVE

The generic construction TR-PKAE gen provides TR-PKAE with all required secu-rity.However,below we show how to construct a TR-PKAE that satis?es all of the above security requirements with the exception that RUF-CTXT is replaced by RUF-TR-CTXT,which is based on a single primitive and is nearly as e?cient as BF-IBE scheme[Boneh and Franklin2003].We argue that in practical applications RUF-TR-CTXT is su?cient since the ciphertexts are submitted before designated time.Moreover,it is desirable for modern authenticated encryption to have one primitive that achieves the desired security properties[Boyen2003]:such solu-tions generally allow for a more e?cient scheme,tighter security bounds and more stringent security.We start with a review of Bilinear Di?e-Hellman Problem. 5.1Bilinear Di?e-Hellman Problem

Let G1and G2be two abelian groups of prime order q.We will use additive notation for the group operation in G1(where aP denotes P added a times for P∈G1,a∈Z q)and multiplicative notation for G2(g a denotes the g multiplied a times for element g of G2).Let e:G1×G1→G2be an admissible bilinear map[Boneh and Franklin2003].The properties of the groups and constructions of e are explained in detail in[Boneh and Franklin2003].

Let G be a Bilinear Di?e-Hellman(BDH)Parameter Generator[Boneh and Franklin2003],i.e.a randomized algorithm that takes positive integer input k, runs in polynomial time in k and outputs prime q,descriptions of G1,G2of order q,description of admissible bilinear map e:G1×G1→G2along with polynomial deterministic algorithms for group operations and e and generators P∈G1,Q∈G2. We say that algorithm A has advantage?(k)in solving the computational BDH Problem(BDHP)for G if there exists k0such that:

(k)=Pr[ q,G1,G2,e ←G(1k),P←G?1,a,b,c←Z?q:

Adv cbdh

A,G

A(q,G1,G2,e,P,aP,bP,cP)=e(P,P)abc]≥?(k),?k>k0(1) We say that G satis?es the computational BDH Assumption if for any randomized ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

16·

polynomial-time algorithm A and any polynomial f∈Z[x]we have Adv cbdh

A,G (k)<

1/f(k)for su?ciently large k

We say that algorithm A has advantage?(k)in solving the decisional BDHP[Boneh and Boyen2004]for G if there exists k0such that:

Adv dbdh

A,G

(k)=|Pr[A(q,G1,G2,e,P,aP,bP,cP,e(P,P)abc)=0]

?Pr[A(q,G1,G2,e,P,aP,bP,cP,T)=0]|≥?(k),?k>k0(2) where the probabilities are taken over the experiment that draws q,G1,G2,e ←G(1k);P←G?1;a,b,c←Z?q;and T←G?2.

We say that G satis?es the decisional BDH(DBDH)Assumption if for any randomized polynomial-time algorithm A and any polynomial f∈Z[x]we have

Adv dbdh

A,G (k)<1/f(k)for su?ciently large k

We also introduce a decisional tripartite Di?e-Hellman(decisional TDHP)prob-lem.A similar problem in the asymmetric setting was introduced in[Laguillaumie et al.2005].In this problem the adversary is given once again the parameters gen-erated by B,random aP,bP,cP∈G1and T∈G1.The adversary has to decide if T=abcP.Even though decisional Di?e-Hellman is easy in G1,6it is still hard to compute abP and the bilinear map appears to be of little help in making the decision in TDHP.More precisely,we say that algorithm A has advantage?(k)in solving the decisional TDHP for G if there exists k0such that:

Adv dtdh

A,G

(k)=Pr[ q,G1,G2,e ←G(1k),P,Q←G?1,a,b←Z?q,T←G?1:

|Pr[A(q,G1,G2,e,P,aP,bP,Q,abQ)=0]?Pr[A(q,G1,G2,e,P,aP,bP,Q,T)=0]|

≥?(k),?k>k0(3) We say that G satis?es the decisional TDH(DTDH)Assumption if for any randomized polynomial-time algorithm A and any polynomial f∈Z[x]we have

Adv dtdh

A,G (k)<1/f(k)for su?ciently large k.

Note that DTDH assumption is stronger than f5736521192e45361066f55dly,hardness of DTDH problem easily implies hardness of DBDH problem.The converse,however,is un-known.

Before we move on to the constructions,we make a few?nal remarks.Firstly, computational BDHP is harder than decisional BDHP.Secondly,hardness of com-putational BDHP automatically implies hardness of computational Di?e-Hellman problem(CDHP)in G1and G2.Also,hardness of the discrete logarithm problem (DLP)in G1implies hardness of DLP in in G2[Menezes et al.1993].However,we remind the reader that the decisional Di?e-Hellman problem is easy in G1.

5.2Description of the Scheme

Let G be a BDH Parameter Generator.Figure5gives a complete description of our construction7.The symmetric encryption scheme used is a straightforward adap-

6Given random aP,bP,Q∈G1,one can check if Q=abP by verifying equality e(aP,bP)= e(Q,P).

7As in[Boneh and Franklin2003],we can weaken the surjectivity assumption on hash function H1.The security proofs and results will hold true with minor modi?cations.We skip the details

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·17 Setup:Given security parameter k∈Z+,the following steps are followed

1:G takes k and generates a prime q,two groups G1,G2of order q,an admissible bilinear map e:G1×G1→G2and arbitrary generator P∈G1.

2:The following cryptographic hash functions are chosen:1)H1:{0,1}?→G?1,

2)H2:G2→{0,1}n for some n,3)H3,H4:{0,1}n×{0,1}n→Z?q and4)

H5:{0,1}n→{0,1}n.These functions will be treated as random oracles in

security considerations.

3:The message space is chosen to be M={0,1}n and the ciphertext space is C=G?1×G?1×{0,1}n×{0,1}n.The general system parameters areπg=

q,G1,G2,e,n,P,H i,i=1 (5)

TRSetup:

1:Choose s∈R Z?q and set P pub=sP.

2:The timed-release public system parameter isπtr=P pub and the master keyδis s∈Z?q.The combined public parameters areπ=πg||πtr=

q,G1,G2,e,n,P,P pub,H i,i=1 (5)

KeyGen:Uniformly choose private key sk=a∈Z?q,and compute the corresponding public key pk as0=aP∈G?1.

TG:On input the time encoding T∈{0,1}n,output sP T where P T=H1(T)

Encrypt:Given the private key sk a of the sender,public key pk b of receiver,plaintext m∈M and time encoding T,encryption is done as follows:1)sampleσ∈R{0,1}n,

compute r1=H3(σ,m)and r2=H4(σ,m);set Q1=r1P T and Q2=r2P;2)

compute L=e(P pub+r1·pk b,(r2+sk a)P T)and symmetric key K=H2(L)and3)

the ciphertext c is set to be c= Q1,Q2,σ⊕K,m⊕H5(σ)

Decrypt:Given ciphertext c= Q1,Q2,c1,c2 encrypted using sk a,pk b and time T,one decrypts it as follows:(1)obtain tkn T=sP T;(2)b K=H2(e(Q2+pk a,sP T+sk b·Q1));

3)retrieve bσ=c1⊕b K and compute b m=c2⊕H5(bσ)and4)verify that Q1=

H3(bσ,b m)P T and Q2=H4(bσ,b m)P;if so,output b m,otherwise output fail.

Fig.5.The TR-PKAE bm scheme

tation of the Fujisaki-Okamoto scheme[Fujisaki and Okamoto1999].We brie?y demonstrate the consistency of the scheme before moving on to security consider-ations.Given ciphertext c= Q1,Q2,σ⊕K,m⊕H5(σ) computed using sk a,pk b and T,we note that in the corresponding Decrypt computations we have1) K=K since e(Q2+pk a,sP T+sk b·Q1)=e(r2P+sk a P,sP T+sk b·r1P T)=e([r2+sk a]P,[s+ r1·sk b]P T)=e([s+r1·sk b]P,[r2+sk a]P T)=e(P pub+r1·pk b,[r2+sk a]P T),3)as in Fujisaki-Okamoto,it follows that σ=σ, m=m and4)Q1=H3( σ, m)P T and Q2=H4( σ, m)P.Thus the original plaintext is retrieved.

5.3Security of the Scheme

The following security results apply to TR-PKAE bm.The hash functions are mod-eled as random oracles[Bellare and Rogaway1995].Below we sketch the main ideas used in the proofs of IND-RTR-KC-CCA2(receiver timed-release con?dential-ity)and RUF-TR-CTXT(receiver timed-release unforgeability),and refer the reader to Appendix A for full details.The proofs of IND-KC-CCA2and TUF-CTXT are more straightforward and the reader is referred to Appendix B.First,we note the con?dentiality properties of the proposed scheme.

and refer the reader to[Boneh and Franklin2003].

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

18·

Theorem5.3.1[IND-RTR-KC-CCA2].Let A be an IND-RTR-KC-CCA2adver-sary that makes q d decryption queries,q2queries to H2and q tok queries to TG. Assume that Adv IND-RTR-KC-CCA2

A,TR?PKAE bm

(k)≥?.Then there exists an algorithm B that

solves computational BDHP with advantage Adv cbdh

B,G (k)≥1

4q2·max(q2,q d) ?e·(1+q tok)

3

and running time O(T ime(A)),where e=2.71828....

Proof.Below we sketch the main idea of the proof.Let a′P,b′P,c′P be the BDH parameters and our goal is to compute e(P,P)a′b′c′.Since the adversary should know sender’s private key,we set sk a=a∈Z?q and make it public.Let us write the bilinear map in the challenge ciphertext as e(P pub+r1·pk b,(r2+a)P T)= e(P pub+r1·pk b,r2P T)·[e(P pub,P T)e(pk b,Q1)]a.Note that,given a,anyone can compute the part[e(P pub,P T)e(pk b,Q1)]a.On the other hand,when we examine e(P pub+r1·pk b,r2P T),we note that we can use adversary to solve a useful problem only if we do not know either r1or r2during the challenge.However,even if adversary manages to compute the bilinear map(which we could not compute)it may not be trivial to extract pk b from the bilinear map with the goal of solving BDHP.Let us set P pub=sP=b′P and suppose during the challenge time T we set P T=c′P(essentially the only time for which we cannot compute token sP T).Let us choose r1in the normal way,but set Q2=r2P=a′P.Then the interesting portion of the challenge bilinear map becomes e(P pub+r1·pk b,r2P T)= e(b′P,a′c′P)e(pk b,r2P T)r1.Note that even if adversary manages to compute this value we still cannot get rid of pk b.However,let us run the simulation once again with the same random tapes,except that1)simulator’s random tape changes right after the challenge ciphertext has been generated,and2)in the challenge ciphertext everything stays the same as in the previous simulation except that r1is a di?erent random number.Then if adversary manages to compute a challenge bilinear map again,we will obtain value of e(b′P,a′c′P)e(pk b,r2P T)r′1where r1=r′f5736521192e45361066f55ding e(b′P,a′c′P)e(pk b,r2P T)r1and e(b′P,a′c′P)e(pk b,r2P T)r′1,we can easily extract e(b′P,a′c′P)and thus solve the BDHP.

Theorem5.3.2[IND-KC-CCA2].Let A be a IND-KC-CCA2adversary that makes q2queries to H2.Assume that Adv IND-KC-CCA2

A,TR?PKAE bm

(k)≥?.Then there exists an al-

gorithm B that solves computational BDHP with advantage Adv cbdh

B,G (k)≥2?

q2

and

running time O(T ime(A)).

The proposed protocol also satis?es the authentication properties speci?ed in the previous section,i.e.,TUF-CTXT and RUF-TR-CTXT.

Theorem5.3.3[RUF-TR-CTXT].Let A be a RUF-TR-CTXT adversary that makes q e encryption queries,q2queries to H2,and q tok queries to TG,and let

Adv RUF-TR-CTXT

A,TR?PKAE bm

(k)≥?.Then there exists an algorithm B with computational

BDHP advantage Adv cbdh

B,G (k)≥?

2·q2·q e·e·(1+q tok)

and running time O(T ime(A)),

where e=2.71828....

Proof.Below we sketch the main idea of the proof.Let a′P,b′P,c′P be the BDH parameters and our goal is to compute e(P,P)a′b′c′.Suppose the adversary manages to compute correctly bilinear map using adaptively chosen receiver’s secret key b and time T.In this case,it can compute the bilinear map e(P pub+r1·bP,(r2+sk a)P T), ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·19 where now the adversary no longer knows sk a.Let us re-write the bilinear map as e(P pub+r1·bP,(r2+sk a)P T)=e(P pub,sk a P T)·[e(P pub,r2P T)·e(Q2+pk a,Q1)b]. The second part of the bilinear map is easily computed using information provided by the adversary and the actual value of r2(obtained from the random oracles).To solve BDHP we can use the?rst part e(P pub,sk a P T)to our advantage by setting P pub=b′P,pk a=a′P and P T=c′P(as before,essentially the only time we cannot compute token sP T).In that case,if the adversary computes the bilinear map,we automatically obtain the value e(b′P,a′c′P),i.e.,the solution to BDHP. Theorem5.3.4[TUF-CTXT].Let A be a TUF-CTXT adversary that makes q e encryption queries and q2queries to H2,and let Adv TUF-CTXT

A,TR?PKAE bm

(k)≥?.Then there

exists an algorithm B with computational BDHP advantage Adv cbdh

B,G (k)≥?

2·q e·q2

and

running time O(T ime(A)).

6.TR-PKE STD:TR-PKE IN THE STANDARD MODEL

The generic TR-PKE gen construction can be shown to be secure in the standard model provided that the underlying primitives are also secure in the standard model. Although e?cient and secure(in the standard model)PKE and signature schemes do exist,until recently all e?cient IBE constructions were shown to be IND-ID-CCA secure only in the random oracle model.The?rst e?cient and fully secure IBE was constructed by Waters[Waters2005]:the construction used a reduction from chosen-plaintext secure2-level HIBE[Gentry and Silverberg2002;Horwitz and Lynn2002;Boneh et al.2005;Boyen and Waters2006](constructed using a semantically secure IBE from the same paper[Waters2005]8)to fully secure IBE using the techniques in[Boneh et al.2006].Following this work,[Kiltz and Galindo 2006;Kiltz2006]directly constructed the?rst e?cient IBE scheme secure in the standard model without use of the HIBE reduction and instead combining the basic IBE scheme of[Waters2005]with techniques?rst described in[Cramer and Shoup 1998].More precisely,[Kiltz and Galindo2006;Kiltz2006]constructed a secure identity based key encapsulation scheme[Cramer and Shoup2003]using which and the hybrid construction technique proposed in[Shoup2000]one can construct e?cient and secure IBE in the standard model.

In this section we give an example TR-PKE scheme in the standard model which uses the same approach as in TR-PKAE bm.The scheme presented here is secure against adaptive IND-CCA2for TR-PKE and secure against non-adaptive IND-RTR-CCA9,given hardness of the decisional BDHP.The di?erence between IND-RTR-CCA2and IND-RTR-CCA is that in the latter the adversary no longer has access to decryption/token oracles once the challenge ciphertext has been generated.Granted that this is a weaker attack,in many practical scenarios this notion still provides su?cient security.Moreover,there is evidence of adaptive IND-RTR-CCA2security for the proposed scheme,although reducing it to well-accepted standard hardness assumption appears to be challenging.More precisely,we also show that the scheme is secure against adaptive IND-RTR-CCA2provided decisional TDHP is hard.

The scheme presented here is an adaptation of the scheme in[Kiltz and Galindo 8The construction was later improved in[Naccache2005]and[Chatterjee and Sarkar2005].

9i.e.,timed-release security against the receiver under“lunchtime”chosen-ciphertext attacks

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

20·

2006].In addition to hardness of decisional BDHP(and decisional TDHP for adap-tive IND-RTR-CCA2),we also require existence of a target collision-resistant hash function h:G1→Z q which can be e?ciently built as shown in[Boyen et al.2005]. Brie?y,for any polynomial-time A,Adv tcr A,h(k)=Pr[x←G1,y←A(x):h(y)= h(x)∧y=x]should be negligible,i.e.given random x∈G1it should be hard to?nd y=x such that h(x)=h(y).Note that if h is injective(which is possible since both G1and Z q are of order q)then it trivially satis?es this requirement. However,in practice standard cryptographic hash functions can also be used.We approach construction of TR-PKE std as follows:?rst we construct a timed-release key encapsulation scheme and then we use the approach given in[Shoup2000]to provide fully functional encryption.

6.1Description of the Scheme

Let G be a BDH Parameter Generator.Figure6gives a complete description of the key encapsulation scheme for TR-PKE std10.The encapsulation scheme is very similar to that given in[Kiltz and Galindo2006]and therefore we refer the reader to the previous work for a consistency proof.Note that if any part of encapsulation is inconsistent,then decapsulation will produce a random result[Cramer and Shoup 2003;Kiltz and Galindo2006].More precisely,the following are the modi?cations to[Kiltz and Galindo2006]:

—The public key of the timed-release server is sP as in[Waters2005](with private key sP2),which is the same as[Kiltz and Galindo2006]except that they slightly simplify it.In addition to that,each receiver has a public/private key pair constructed in the same way,i.e.,a receiver has public key(bP,bP3)and private key bP2where bP3is used only for key veri?cation.We denote P T=H(T)= U′+ i T i V i to be the hash of T rather than the identity,constructed in the same way as in[Waters2005].

—To encrypt for time T,we simply add the public keys sP of timed-release server and bP of receiver and encapsulate for time T the same way as[Kiltz and Galindo 2006]encapsulates for identity P T=H(T)with the public key sP+bP.

—To decapsulate,the secret information needed in[Kiltz and Galindo2006]is the identity decryption key{sP2+t H(T),tP}.In our case,this information will be published by the Timed-Release server on date T.However,this is insu?cient since the encapsulation was done using sP+bP and not simply sP as the public key.This can easily overcome by having receiver add bP2(his secret key)to sP2+t H(T)and obtain{(sP2+bP2)+t H(T),tP}which is exactly the decryption key that would be required in[Kiltz and Galindo2006]to decapsulate information that was encapsulated using sP+bP.

10If only IND-RTR-CCA and IND-CCA2are required,then one can simplify the encapsulation scheme further as follows:1)generator P3is no longer required and public key now is simply b bP;2)instead of h(rP T+pk1),one can compute h(rP)with corresponding modi?cations in the decapsulation.One can show that the resulting encapsulation scheme is IND-KEM-RTR-CCA and f5736521192e45361066f55ding Shoup’s hybrid approach[Shoup2000],the resulting TR-PKE scheme is IND-RTR-CCA and IND-CCA2secure.This saves two bilinear maps in the encryption, but the encapsulation scheme is demonstrably insecure against adaptive IND-KEM-RTR-CCA2. ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

·21 Setup:Given security parameter k∈Z+,the following steps are followed

1:G takes k and generates a prime q,where2k

P,P2,P3∈G1.

2:A cryptographic hash function h:G1→Z q is chosen.

3:Random U′∈G1and V=(V1,...,V n)∈G n1are chosen.Also,ran-dom L1,L2∈G1are chosen.The general system parameters areπg=

q,G1,G2,e,n,U′,V,P,P2,P3,L1,L2,h

TRSetup:

1:Choose s∈R Z q and set P pub=sP.The private key is Q=sP2.

2:The timed-release public system parameter isπtr=P pub and the mas-ter keyδis Q.The combined public parameters areπ=πg||πtr=

q,G1,G2,e,n,U′,V,P,P2,P3,L1,L2,h,P pub .

KeyGen:Uniformly choose b b∈Z?q.The public key is pk={0=b bP,b bP3},and the private key is b bP2.

TG:On input the time encoding T∈{0,1}n,pick random t∈Z?q and output{Q+tP T,tP} where P T=U′+P i T i·V i and T1||T2...||T n is bitwise representation of T.

Encapsulate:Given the public key pk={pk1,pk2}of the receiver and time encoding T, encapsulation is done as follows:1)verify consistency of pk by checking e(pk1,P3)=

e(pk2,P);2)sample r∈R Z q,compute C1=r[h(rP T+pk1)L1+L2],C2=rP and

C3=rP T.The key encapsulated is K=e(P pub+pk1,P2)r,while the encapsulation

is C= C1,C2,C3 .

Decapsulate:Given encapsulation C= C1,C2,C3 using pk with corresponding pri-vate key b bP2and time T,one decapsulates it as follows:(1)obtain tkn T=

{Q+tP T,tP}={d1,d2};(2)pick random r1,r2∈Z q and compute the encapsu-

lated key b K=e(C2,d1+b bP2+r1[h(C3+pk1)L1+L2]+r2P T)

.

e(C3,d2+r2P)·e(r1P,C1)

Fig.6.The TR-PKE std key encapsulation scheme in the standard model

—To provide security against adaptive IND-KEM-RTR-CCA2,(receiver timed-release con?dentiality)we also slightly modify what goes inside the cryptographic hash function h.In[Kiltz and Galindo2006],the authors used h(rP).In our case, we use h(rP T+bP)which makes it harder for an adversary to launch successful adaptive attacks.

6.2Security of the Scheme

The security proofs are modi?cations of[Waters2005]and[Kiltz and Galindo 2006]and are provided in Appendix C,where we discuss the relevant modi?cations and reduction analysis.The proofs are given with respect to notions IND-KEM-CCA2and IND-KEM-RTR-CCA which are de?ned almost identically to IND-CCA2 and IND-RTR-CCA except that:decryption queries are replaced by decapsulation queries;and during the challenge we provide an encapsulation and choose at ran-dom whether to give to the adversary the encapsulated key or a random key;the adversary’s goal is to decide which key was given.

Below we sketch the proof of receiver timed-release con?dentiality IND-KEM-RTR-CCA(and IND-KEM-RTR-CCA2given hardness of decisional TDHP).One notable(but expected)property is that due to the extra binding in users’public keys,the decryption oracle in the simulation given in the proof no longer requires a receiver’s private key.

ACM Transactions on Information Systems and Security,Vol.V,No.N,20YY.

本文来源：https://www.bwwdw.com/article/ih3q.html