# Patent

## Title
Advancing a committed transaction time

## Abstract

Transaction systems and methods for advancing a committed time in the future are described herein. In the present transaction systems and methods, the first end can be permitted to pre-hatch a time capsule signature before the committed time. The time capsule signature scheme here is conducted based on an identity-based trapdoor relation (IDTR). Moreover, an extended time capsule signature scheme is conducted based on an extended identity-based trapdoor relation (IDTR). By using an extended IDTR primitive, the present transaction systems and methods can distinguish the time capsule signature is validated before or after the committed time t.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims the benefit of priority from the prior U.S. provisional application 61/047,236, filed Apr. 23, 2008, the entire contents of which are incorporated herein by reference.


BACKGROUND
In the conventional signature scheme used in the E-cornmerce transaction, the validity of a signature value is determined at the point of signature generation and never changes. Signers cannot generate the so-called ‘future signature’ which is not currently valid but becomes valid from a future time t.
A naive way to achieve this is signing with a statement such as “the signature of message m becomes valid from the future time t.” This, however, has several drawbacks. First, and least serious, the verifier is required to be aware of the current time. When time is generalized to arbitrary events (i.e., ‘the signature of message m becomes valid if the event e happens’), this becomes even more problematic. More seriously, however, in the naive solution the signer loses control over the validity of the future signature, i.e. even the real signer cannot make the signature valid before the time t. This means the signer has to wait until time t. It could be undesirable in certain situations. For example, in the case of debt repayment, after a borrower signed a check to indicate the repayment day (e.g. due day), he may have the desire to repay his debt earlier to improve his credit history.
Alternatively, the signer can issue a new, independent signature of message m before time t. This solution, however, can also be undesirable in certain situations. For example, in case the message m carries some monetary value, the first end needs to make sure that no “double spending” occurs (i.e., to somehow revoke the original signature, so that it does not become valid at time t).
Therefore, it is necessary to figure out a solution where the signer can issue a future signature so that at least the following properties are satisfied:

    (1) At the time of creation, the verifier is sure that the signature will become valid by time t, even if the signer refuses to cooperate after she produces the future signature.
    (2) The legal signer can make the future signature valid at any time after the initial creation.


To realize these properties in E-Commerce platforms, a new primitive, which has a great promise to be a very useful tool, is called Time Capsule Signature.
A time capsule signature involves a first end (such as a signer), a second end (such as a verifier) and a time server. The first end can issue a future signature indicated by a committed time t, and enjoys the following properties: first, the second end can verify immediately that the signature will become valid at time t; secondly, the signature will automatically become valid at the committed time t, even without the cooperation of the first end; and moreover, the first end has a privilege to make the signature valid before time t. The action of validating the signature before the time t is known as pre-hatch, as opposed to hatch the signature at time t when some additional information is published by the time server.
Moreover, in some scenarios, it is needful to distinguish a pre-hatched signature from a hatched signature. In the above debt repayment case, a pre-hatched signature has to be identified when a signer intentionally pre-hatches the signature for increasing his credit history. On the other hand, under the property of indistinguishability of the conventional signature scheme, the time server has to be fully trusted, otherwise, there is no way to tell if a signature which becomes valid before time t is generated by the actual signer or a cheating time server.
It is therefore desirable to have systems and methods for advancing the committed time t based on the willing of the first end. Meanwhile, the systems and methods can distinguish a pre-hatched signature from a hatched signature.
SUMMARY
The subject innovation provides a transaction system and a transaction method for advancing a committed time in the future. Currently used techniques that model transaction actions in an E-commerce platform limit the variety of E-Commerce because a first end loses control of the committed time t once a signature is produced. Further, current E-commerce transaction techniques prevent the first end from validating the signature before the committed time t.
Compared to the current E-commerce transaction technology, the novel systems and methods of the claimed subject matter provide the possibility of realizing various transactions in E-commerce. Unlike the conventional E-commerce transaction technology, the variety of E-commerce is provided because the first end has a power to validate the signature before the committed time t. In addition, the systems and methods of the subject innovation can distinguish if the signature is hatched or pre-hatched.
The following presents a simplified summary of the innovation in order to provide a basic understanding of some aspects described herein. This summary is not an extensive overview of the disclosed subject matter. It is intended to neither identify key or critical elements of the disclosed subject matter nor delineate the scope of the subject innovation. Its sole purpose is to present some concepts of the disclosed subject matter in a simplified form as a prelude to the more detailed description that is presented later.
The subject innovation provides an improved transaction system and method for providing variety of E-commerce. In accordance with one aspect of the disclosed subject matter, an transaction system provides variety of E-Commerce, which comprises: a first end coupled to open distributed information network or Internet for conducting electronic transaction; a second end coupled to the Internet for verifying the electronic transaction; an time server coupled to the network for arbitrating the electronic transaction between the first end and the second end. The first end can generate a time capsule signature on a message for a committed time and a sampled witness value based on the committed time. The first end can generate a pre-hatched signature by combining or relating the time capsule signature and the sampled witness value. The second end can validate the pre-hatched signature at a validated time before the committed time.
In accordance with another aspect of the disclosed subject matter, the transaction system and method further can identify whether the time capsule signature is hatched or pre-hatched. It means that the transaction system and method can distinguish the time signature is validated before or after the committed time t.
The following description and the annexed drawings set forth in detail certain illustrative aspects of the disclosed subject matter. These aspects are indicative, however, of but a few of the various ways in which the principles of the innovation may be employed. The disclosed subject matter is intended to include all such aspects and their equivalents. Other advantages and distinctive features of the disclosed subject matter will become apparent from the following detailed description of the innovation when considered in conjunction with the drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
Non-limiting and non-exhaustive embodiments of the invention are described with reference to the following figures, wherein like reference numerals refer to like parts throughout the various views unless otherwise specified.
FIG. 1 is a demonstrative transaction system for providing variety of E-commerce, in accordance with an embodiment of the invention.
FIG. 2a illustrates a process for hatching the time capsule signature, in accordance with one of embodiments of the invention.
FIG. 2b illustrates a process for pre-hatching the time capsule signature, in accordance with one of embodiment of the invention.
FIG. 3 illustrates a process for identifying the time when the time capsule signature is validated, in accordance with one of embodiment of the invention.



DETAILED DESCRIPTION
Embodiments of systems and methods for advancing a committed time in E-commerce transaction are described herein. In the following description, numerous specific details are set forth to provide a thorough understanding of the embodiments. One skilled in the relevant art will recognize, however, that the techniques described herein can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring certain aspects.
Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrase “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.
The subject invention relates to transaction systems and methods for providing variety of E-commerce by advancing a committed time. To this end, embodiments of the invention include techniques for permitting a first end to validate the time capsule signature before the committed time. Further, embodiments of the invention include techniques for maintaining the security in the E-commerce transaction while the first end advances the committed time.
FIG. 1 is a demonstrative transaction system 100 for providing variety of E-commerce, in accordance with an embodiment of the invention. System 100 and the systems and processes explained below may constitute machine-executable instructions embodied within a machine (e.g., computer) readable medium, which when executed by a machine will cause the machine to perform the operations described. Additionally, the systems and processes may be embodied within hardware, such as an application specific integrated circuit (ASIC) or the like. The order in which some or all of the process blocks appear in each process should not be deemed limiting. Rather, it should be understood by a person of ordinary skill in the art having the benefit of the instant disclosure that some of the process blocks may be executed in a variety of orders not illustrated.
Transaction system 100 illustrated by FIG. 1 can include a first end 110 coupled to open distributed information network or Internet for conducting electronic transaction, a second end 120 coupled to Internet for verifying the electronic transaction and an time server 130 coupled to Internet for arbitrating the electronic transaction between the first end and the second end. The time server 130 does not contact both the first end 110 and the second end 120, and has no need to know anything from both the first and second end. Moreover, the first end 110 comprises a means that can generate a time capsule signature on a message for a committed time and a sampled witness value based on the committed time. The first end 110 further comprises a means that can generate a pre-hatched signature by combining or relating the time capsule signature and the sampled witness value. The second end 120 comprises a means that can validate the pre-hatched signature at a validated time before the committed time. In an exemplary embodiment, the first end 110 can be a credential releaser, and the second end can be a credential receiver. Furthermore, the first end can be a signer, and the second end can be a verifier.
FIGS. 2 and 3 illustrate methodologies in accordance with the disclosed subject matter. For simplicity of explanation, the methodologies are depicted and described as a series of acts. It is to be understood and appreciated that the subject innovation is not limited by the acts illustrated and/or by the order of acts, for example acts can occur in various orders and/or concurrently, and with other acts not presented and described herein. Furthermore, not all illustrated acts may be required to implement the methodologies in accordance with the disclosed subject matter. In addition, those skilled in the art will understand and appreciate that the methodologies could alternatively be represented as a series of interrelated states via a state diagram or events. Additionally, it should be further appreciated that the methodologies disclosed hereinafter and throughout this specification are capable of being stored on an article of manufacture to facilitate transporting and transferring such methodologies to computers. The term article of manufacture, as used herein, is intended to encompass a computer program accessible from any computer-readable device, carrier, or media.
Referring now to FIG. 2a, FIG. 2a demonstrates an E-commerce transaction method for validating a time capsule signature at a committed time t, which comprises the following steps. At first, in Step 210, a first public key and a first secret key are set by the time server; meanwhile, a second public and a second public key are set by the first end. In Step 220, the first end generates the time capsule signature σ′t on a message m for the committed time t as well as a sampled witness value d based on the committed time t. The first end then stores the sampled witness value d. In Step 230, the second end checks if the time capsule signature σ′t is a valid time capsule signature. If the time capsule signature is not valid before the committed time t, the time server publishes a time-related information zT based on the committed time t and the first secret key, as indicated in Step 240. Step 250 shows that both the first end and the second end are able to generate a hatched signature by combining or relating the time capsule signature and an inverted witness value {circumflex over (d)}. In Step 260, the second end checks the validity of the hatched signature and validates the message m at committed time t.
Referring now to FIG. 2b, FIG. 2b illustrates an E-commerce transaction method for permitting the first end to validate a time capsule signature before the committed time t. The exemplary transaction method comprises the following steps. In Step 215, the timer server sets a first public key and a first secret key; meanwhile, the first end sets a second public key and a second secret key. In Step 225, the first end generates the time capsule signature σ′t on a message m for the committed time t and a sampled witness value d based on the committed time t. The first end then stores the sampled witness value d. In Step 235, the second end checks if the time capsule signature σ′t is a valid time capsule signature. If the first end wants to validate the time capsule signature σ′t before the committed time t, the first end retrieves the sampled witness value d and generates a pre-hatched signature by combining or relating the time capsule signature and the sampled witness value d, as showed in Step 245. The second end, in Step 255, checks the validity of the pre-hatched signature and validates the message m before the committed time t.
Referring now to FIG. 3, FIG. 3 further illustrates an E-commerce transaction method for distinguishing a time capsule signature is pre-hatched or hatched. As discussed above, in some scenarios, there are demands to distinguish a pre-hatched signature from a hatched signature. In the case of debt repayment, as an example, if a borrower repays his debt before the committed date, he can improve his credit history or get extra reward. Then the signature for validating the payment check should be determined on whether it is pre-hatched or hatched. In this exemplary transaction method illustrated in FIG. 3, Steps 310 through 330 are the same as Steps 215 through 235 of FIG. 2(b). Further, in Step 340, if the first end would like to validate the signature before the committed time t, a pre-hatched signature is generated by combining or relating the time capsule signature and the sampled witness value d. In Step 350, the second end prints out the sampled witness value d before verifying the pre-hatched signature. The second end, in Step 360, checks the validity of the pre-hatched signature and validates the message m. There are two different algorithms are used to check the validity of the signature to be validated at this step. One is “used to verify the pre-hatched signature, and the other is used to verify the hatched signature. Accordingly, the second end can identify the time t1 is prior to the committed time t, as shown in Step 370.
In one embodiment, a time capsule signature scheme can extended to achieve a property called Hiding. The Hiding property can capture a malicious time server who aims to forge a sampled for a given commitment.
Moreover, in the following embodiments the first public key is exemplarily replaced by a public time release key (tpk), and the first secret key is exemplarily replaced by a secret time release key (tsk). The second public key is exemplarily replaced by a user public key (upk), and the second secret key is exemplarily replaced by a user secret key (usk).
<Embodiment 1> Definition of Time Capsule Signature:
A time capsule signature scheme comprises eight PPT algorithms including: TSSetup, UserSetup, TSig, TVer, TRelease, Hatch, PreHatch and Ver. The definition of these eight algorithms are showed as follows:

    
    
        1. TSSetup (Time Server Key Setup): On input 1k where k ε is a security parameter, it generates a public time release key (tpk) and a secret time release key (tsk).
        2. UserSetup (User Key Setup): On input 1k, it generates a user public key (upk) and a secret key pair (usk).
        3. TSig (Time Capsule Signature Generation): On input (m, σ′t, usk, tpk, t), where t is a time value from which the signature will become valid. It outputs a time capsule signature σ′t.
        4. TVer (Time Capsule Signature Verification): On input (m, σ′t, usk, upk, t) it returns 1 (accept) or 0 (reject). A time capsule signature σ′t is said to be valid if TVer returns 1 on it.
        5. TRelease (Time Release): At the beginning of each time period T, zT←TRelease(T, tsk) is published by the time server.
        6. Hatch (Signature Hatch): On input (m, σ′t, upk, tpk, zt) both the first end and second end can run this algorithm to get a hatched signature σt from a valid time capsule signature σ′t.
        7. PreHatch (Signature Prehatch): On input (m, σ′t, usk, tpk, t), the signer can run the algorithm to get a prehatched signature σt of a valid time capsule signature σ′t before time t. However, if σ′t is not valid, namely, TVer(m, σ′t, upk, tpk, t)=0, then PreHatch should return ⊥ which stands for unsuccessful prehatch.
        8. Ver (Signature Verification): On input (m, σ′t, usk, tpk, t), it returns 1 (accept) or 0 (reject).
    
    


<Embodiment 2> Adversarial Model:
There are three types of adversaries, I, II and III. I simulates a malicious signer whose aim is to produce a time capsule signature σ′t, which looks good to a verifier, but cannot be hatched at time t. II simulates a malicious verifier who wants to hatch a time capsule signature before time t. III simulates a malicious time server who wants to forge a signature. Note that attacks launched by an outsider who wants to forge a signature can also be captured by III. In the following, let k ε  be a security parameter.
Game I: Let SI be the game simulator.

    
    
        1. SI executes TSSetup(1k) to get (tpk, tsk).
        2. SI runs I on tpk. During the simulation, I can make queries onto TRelease.
        3. I is to output (m*, t*, σ′*, upk).
        4. SI executes TRelease(t*, tsk) to get Z*t, and then executes Hatch(m*, σ′*, upk, tpk, z*t) to get σ*.
        I wins if TVer(m*, σ′*, upk, tpk, t)=1 and Ver(m*, σ*, upk, tpk, t)=0.
    
    


A time capsule signature scheme is secure in Game I if for every PPT algorithm I, it is negligible for I to win the game. Note that there is no restriction put on the generation of user public key upk. This is natural as in practice, I is normally the one who generates (upk, usk).
Game II: Let SII be the game simulator.

    
    
        1. II executes TSSetup(1k) to get (tpk, tsk) and UserSetup(1k) to get (upk, usk).
        2. SII runs II on tpk and upk. During the simulation, II can make queries onto TSig, TRelease and PreHatch.
        3. II is to output (m*, t*, σ*).
        II wins if Ver(m*, σ*, upk, tpk, t*)=1 and II has never queried TRelease(t*) and PreHatch (m*, t*,·).
    
    


A time capsule signature scheme is secure in Game II if for every PPT algorithm II, it is negligible for II to win the game.
Game III: Let SIII be the game simulator.

    
    
        1. SIII executes TSSetup(1k) to get (tpk, tsk) and UserSetup(1k) to get (upk, usk).
        2. SIII runs III on tpk and tsk. During the simulation, III can make queries onto TSig, TRelease and PreHatch.
        3. III is to output (m*, t*, σ*).
        III wins if Ver(m*, σ*, upk, tpk, t*)=1 and III has never queried TSig(m*,·) for time t*.
    
    


A time capsule signature scheme is secure in Game III if for every PPT algorithm III, it is negligible for II to win the game.
<Embodiment 3> Identity-Based Trapdoor Relation (IDTR):
A binary relation R is a subset of {0,1}*×{0,1}* and the language £R is the set of α's for which there exist β such that (α, β) ε R, i.e., £R={α|∃β[(α, β) ε R]}. It assumes that (1) there is an efficient algorithm to decide whether α ε £R or not, (2) if (α, β) ε R, then the length of β is polynomially bounded in |α| and (3) there exists a short description DR which specifies the relation R.
An identity-based trapdoor relation (IDTR) is a set of relations ={Rid|id ε }, where each relation Rid is called a trapdoor relation and there is a master trapdoor  for extracting the trapdoor tdid of each Rid. Formally, IDTR is specified by the following five probabilistic polynomial-time (PPT) algorithms (Gen, Sample, Extract, Invert, Check).

    
    
        1. Gen: This algorithm is used to generate ={Rid|id ε } where  is a finite set of indices. Gen(1k) returns  (the description of ) and  (the master trapdoor).
        2. Sample: This sampling algorithm takes (, id) as input and (id) returns a random commitment c and a sampled witness d such that (c,d) ε Rid.
        3. Extract: This algorithm is used to extract the trapdoor of each relation by using . , (id) returns the trapdoor tdRid of relation Rid.
        4. Invert: This algorithm is used to find a sampled witness d for a given c ε £Rid by using the trapdoor tdRid. If c ε £Rid, then InverttdRid (c) returns a witness {circumflex over (d)} such that (c, {circumflex over (d)}) ε Rid).
        5. Check: This algorithm is used to check the validity of a witness d on the commitment c. If (c,d) ε Rid, then (c, d) returns 1 (accept). Otherwise, it returns 0 (reject).
    
    


Properties: One-wayness requires that no one is able to find the witness of a commitment if the trapdoor information is not given. Soundness requires that no one can produce a commitment whose witness cannot be found using Invert.

    
    
        One-wayness: Let OExtract be an oracle simulating the trapdoor extraction procedure Extract and Query(A, OExtract) the set of queries an algorithm A asked to OExtract. It states that the following probability is negligible for all PPT algorithm A=(A1, A2):
    
    






  Pr
  ⁡
  
    [
    
      
        
          
            Check
            
              
                D
                R
              
              ,
              
                id
                ⋆
              
            
          
          ⁡
          
            (
            
              
                c
                ⋆
              
              ,
              
                d
                ˇ
              
            
            )
          
        
        =
        
          
            1
            ⩓
            
              
                id
                ⋆
              
              ∉
              
                Query
                ⁡
                
                  (
                  
                    A
                    ,
                    
                      O
                      Extract
                    
                  
                  )
                
              
            
          
          ❘
          
            

          
          ⁢
          
            
              (
              
                
                  D
                  R
                
                ,
                
                  mtd
                  R
                
              
              )
            
            ←
            
              Gen
              ⁡
              
                (
                
                  1
                  k
                
                )
              
            
          
        
      
      ;
      
        
          (
          
            
              id
              ⋆
            
            ,
            h
          
          )
        
        ←
        
          
            A
            1
            
              O
              Extract
            
          
          ⁡
          
            (
            
              D
              R
            
            )
          
        
      
      ;
      
        

      
      ⁢
      
        
          (
          
            
              c
              ⋆
            
            ,
            d
          
          )
        
        ←
        
          
            Sample
            
              D
              R
            
          
          ⁡
          
            (
            
              id
              ⋆
            
            )
          
        
      
      ;
      
        
          d
          ˇ
        
        ←
        
          
            A
            2
            
              O
              Extract
            
          
          ⁡
          
            (
            
              
                id
                ⋆
              
              ,
              
                c
                ⋆
              
              ,
              h
            
            )
          
        
      
    
    ]
  




    
    
        Soundness: It is required that the following probability should be negligible for all algorithm B:
    
    






  Pr
  ⁡
  
    [
    
      
        
          
            
              R
              
                id
                ⋆
              
            
            ∈
            R
          
          ⩓
          
            
              c
              ⋆
            
            ∈
            
              L
              
                R
                
                  id
                  ⋆
                
              
            
          
          ⩓
          
            
              Check
              
                
                  D
                  R
                
                ,
                
                  id
                  ⋆
                
              
            
            ⁡
            
              (
              
                
                  c
                  ⋆
                
                ,
                
                  d
                  ˇ
                
              
              )
            
          
        
        =
        
          0
          ❘
          
            

          
          ⁢
          
            
              (
              
                
                  D
                  R
                
                ,
                
                  mtd
                  R
                
              
              )
            
            ←
            
              Gen
              ⁡
              
                (
                
                  1
                  k
                
                )
              
            
          
        
      
      ;
      
        
          (
          
            
              c
              ⋆
            
            ,
            
              id
              ⋆
            
          
          )
        
        ←
        
          B
          ⁡
          
            (
            
              
                D
                R
              
              ,
              
                mtd
                R
              
            
            )
          
        
      
      ;
      
        

      
      ⁢
      
        
          td
          
            R
            
              id
              ⋆
            
          
        
        ←
        
          
            Extract
            
              mtd
              R
            
          
          ⁡
          
            (
            
              id
              ⋆
            
            )
          
        
      
      ;
      
        
          d
          ˇ
        
        ←
        
          
            Invert
            
              td
              
                R
                
                  id
                  ⋆
                
              
            
          
          ⁡
          
            (
            
              c
              ⋆
            
            )
          
        
      
    
    ]
  




ID-THIR has an ambiguity property which requires that witness {circumflex over (d)} inverted from c given tdRid is computationally indistinguishable from d obtained from (id) for the same commitment c.
<Embodiment 4> Implementations of IDTR in Random Oracle Model:
One concrete construction of IDTR is proposed based on Boneh-Franklin's IBE whose security has been proven in the random oracle model. An Identity-Based Encryption (IBE) scheme consists of four PPT algorithms including: Setup, KeyGen, Encrypt, Decrypt. The Boneh-Franklin scheme is described as follows:

    
    
        1. Setup: Given a security parameter k ε , generate a prime q, two groups 1,2 of order q, and an admissible bilinear map {tilde over (e)}: 1,×1→2, where |q| is some polynomial in k. Choose a random generator P ε 1, pick a random s ε *q and set Ppub=sP. Choose a cryptographic hash function H1:{0,1}*→1, another hash function H2:2→{0,1}k, and the security analysis will view H1, H2 as random oracles [4]. The message space is M={0,1}k. The ciphertext space is C=1×{0,1}k. The system public key is mpk=q,1,2,{tilde over (e)}, P, Ppub,H1,H2 The master secret key msk is s ε *q.
        2. KeyGen: For a given string id ε {0,1}* the algorithm computes Qid=H1(id) ε1, and sets the private key skid to be SQid where s is the master secret key.
        3. Encrypt: To encrypt m ε M under the public key id, the algorithm computes Qid=H1(id) ε 1, chooses a random r ε *q, and sets the ciphertext to be c=rP,m⊕H2(gid r ) where gid={tilde over (e)}(Qid,Ppub) ε 2.
        4. Decrypt: Given the private key skid ε 1, a ciphertext c=c1, c2 ε C can be decrypted by computing c2⊕H2({tilde over (e)}(skid, c1))=m.
    
    


An IDTR based on the IBE above is constructed as follows:

    
    
        1. Gen: Run Setup(1k), and set £R=C, =mpk, and =msk.
        2. Sample: Given  and id, randomly pick m ε M and compute c=Encryptid (m). Let r ε q* be the randomness used in Encrypt. Set witness d=rQid, Ppub, m.
        3. Extract: Given a string id ε {0,1}*, compute skid=KenGenmpk,msk(id), and set tdRid=skid.
        4. Invert: Given trapdoor tdRid ε 1 and a commitment c=c1, c2 ε C, compute m=Decryptskid (c), and set the witness {circumflex over (d)}=tdRid, c1, m.
        5. Check: Given , id, c=c1, c2 ε C, d=d1, d2, d3 (where d1, d2 ε 1, and d3 ε M), if d2=Ppub, ê(d1,P)=ê(c1, Qid), and c2=d3⊕H2 (ê(d1, d2)), return 1. Else if d1=tdRid, d2=c1, ê(d1, P)=ê(Ppub, Qid) and c2=d3⊕H2(ê(d1, d2)), return 1. Otherwise, return 0.
    
    


In the game of one-wayness, an adversary A has access to the Extract oracle of all id other than id*. This oracle is simulated by performing KeyGen of the underlying IBE scheme. A wins if it can find secret key skid* and plaintext m*. However, the semantic security of the underlying IBE attains that any PPT adversary will have negligible advantage in distinguishing m* with another m in M. If A succeeds, it is easy to see that we can also distinguish m*, which contradicts the security of the underlying IBE scheme.
In the game of Soundness, an adversary B wins if it can generate a value c* which is not able to decrypt under skid*. In the underlying IBE scheme, this will not be the case even when B knows msk. Given id*, skid* can always be properly generated with the knowledge of msk. As long as c* is in the ciphertext domain, a valid plaintext m* can always be retrieved.
<Embodiment 5> Implementations of IDTR in Standard Model:
Another concrete construction of IDTR is proposed based on Waters' IBE whose security has been proven in the standard model. An Identity-Based Encryption (IBE) scheme consists of four PPT algorithms including: Setup, KeyGen, Encrypt, Decrypt. The Waters scheme is described as follows:

    
    
        1. Setup: Given a security parameter k ε , generate a prime p, two groups 1,2 of order p, and an admissible bilinear map {tilde over (e)}: 1,×1→2, where |p| is some polynomial in k. Choose a random generator g ε 1, pick a random α ε q* and set g1=gα. Choose random values g2, u′ ε 1, and a random k-length vector U=(ui), whose elements are chosen uniformly at random from 1. The message space is M ⊂ 2. The ciphertext space is C=2×1×1. The system public key is mpk=p, 1, 2, é, k, g, g1, g2, u′, U. The master secret key msk is g2α.
        2. KeyGen: Let v be an k-bit string representing an identity id, vi denote the ith bit of v, and V ⊂ 1, . . . , k be the set of all i for which vi=1. (V is the set of indices for which the bit-string v is set to 1.) Randomly select r ε p* and construct the private key skid as:
    
    






  
    sk
    id
  
  =
  
    〈
    
      
        
          
            g
            2
            α
          
          (
          
            
              u
              ′
            
            ⁢
            
              
                ∏
                
                  i
                  ∈
                  v
                
              
              ⁢
              
                
              
              ⁢
              
                u
                i
              
            
          
          )
        
        r
      
      ,
      
        g
        r
      
    
    〉
  




    
    
        3. Encrypt: To encrypt m ε M for an identity v, randomly select t ε p* and construct the ciphertext c as:
    
    






  c
  =
  
    〈
    
      
        
          
            
              e
              ^
            
            ⁡
            
              (
              
                
                  g
                  1
                
                ,
                
                  g
                  2
                
              
              )
            
          
          t
        
        ⁢
        m
      
      ,
      
        g
        t
      
      ,
      
        
          (
          
            
              u
              ′
            
            ⁢
            
              
                ∏
                
                  i
                  ∈
                  v
                
              
              ⁢
              
                
              
              ⁢
              
                u
                i
              
            
          
          )
        
        t
      
    
    〉
  




    
    
        4. Decrypt: Given the private key skid=sk1, sk2, a ciphertext c=c1, c2, C3 ε C can be decrypted by computing
    
    






  
    
      
        
          c
          1
        
        =
        
        ⁢
        
          
            
              e
              ^
            
            ⁡
            
              (
              
                
                  sk
                  2
                
                ,
                
                  c
                  3
                
              
              )
            
          
          
            
              e
              ^
            
            ⁡
            
              (
              
                
                  sk
                  1
                
                ,
                
                  c
                  2
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  
                    e
                    ^
                  
                  ⁡
                  
                    (
                    
                      
                        g
                        1
                      
                      ,
                      
                        g
                        2
                      
                    
                    )
                  
                
                t
              
              ⁢
              m
            
            )
          
          ⁢
          
            
              
                e
                ^
              
              (
              
                
                  g
                  r
                
                ,
                
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                  t
                
              
              )
            
            
              
                e
                ^
              
              (
              
                
                  g
                  2
                  α
                
                ,
                
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                  r
                
                ,
                
                  g
                  t
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  
                    e
                    ^
                  
                  ⁡
                  
                    (
                    
                      
                        g
                        1
                      
                      ,
                      
                        g
                        2
                      
                    
                    )
                  
                
                t
              
              ⁢
              m
            
            )
          
          ⁢
          
            
              
                e
                ^
              
              (
              
                g
                ,
                
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                  
                    r
                    ⁢
                    
                      
                    
                    ⁢
                    t
                  
                
              
              )
            
            
              
                (
                
                  
                    
                      e
                      ^
                    
                    (
                    
                      
                        g
                        
                          1
                          ,
                        
                      
                      ⁢
                      
                        g
                        2
                      
                    
                    )
                  
                  t
                
                )
              
              ⁢
              
                
                  e
                  ^
                
                (
                
                  
                    
                      (
                      
                        
                          u
                          ′
                        
                        ⁢
                        
                          
                            ∏
                            
                              i
                              ∈
                              v
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            u
                            i
                          
                        
                      
                      )
                    
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      t
                    
                  
                  ,
                  g
                
                )
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        m
      
    
  




An IDTR based on Waters's IBE above is constructed as follows:

    
    
        1. Gen: Given k ε , execute (mpk,msk)←Setup(1k) and set £R=C, =mpk, and =msk.
        2. Sample: Given  and id, randomly pick m ε 2 and compute c=Encryptid(m). Let t ε p* be the randomness in producing c. Set witness d to
    
    






  d
  =
  
    〈
    
      
        
          g
          2
          t
        
        (
        
          
            u
            ′
          
          ⁢
          
            
              ∏
              
                i
                ∈
                v
              
            
            ⁢
            
              
            
            ⁢
            
              u
              i
            
          
        
        )
      
      ,
      
        g
        2
      
      ,
      
        c
        3
      
      ,
      m
    
    〉
  




    
    
        3. Extract : Let v be an k-bit identity id, compute skid=KenGenmpk;msk(id) and set tdRid=skid.
        4. Invert: Given trapdoor tdRid and a commitment c=c1, C2, C3 εC, compute m=Decryptskid(c), and set the witness to

{circumflex over (d)}=sk1, c2, sk2, c3, m

    
    





  
    
      
        5.
        ⁢
        
          
        
        ⁢
        Check
        ⁢
        
          :
        
        ⁢
        
          
        
        ⁢
        Given
        ⁢
        
          
        
        ⁢
        
          D
          R
        
      
      ,
      id
      ,
      
        c
        =
        
          
            〈
            
              
                c
                1
              
              ,
              
                c
                2
              
              ,
              
                c
                3
              
            
            〉
          
          ∈
          C
        
      
      ,
      
        d
        =
        
          〈
          
            
              d
              1
            
            ,
            
              d
              2
            
            ,
            
              d
              3
            
            ,
            
              d
              4
            
            ,
            
              d
              5
            
          
          〉
        
      
    
    ⁢
    
      
    
  




  
    
      
    
    ⁢
    
      
        (
        
          
            where
            ⁢
            
              
            
            ⁢
            
              d
              1
            
          
          ,
          
            d
            2
          
          ,
          
            d
            3
          
          ,
          
            
              d
              4
            
            ∈
            
              G
              12
            
          
          ,
          
            
              and
              ⁢
              
                
              
              ⁢
              
                d
                5
              
            
            ∈
            M
          
        
        )
      
      ,
      
        
          if
          ⁢
          
            
          
          ⁢
          
            d
            2
          
        
        =
        
          
            g
            1
          
          (
          
            
              u
              ′
            
            ⁢
            
              
                ∏
                
                  i
                  ∈
                  v
                
              
              ⁢
              
                
              
              ⁢
              
                u
                i
              
            
          
          )
        
      
      ,
      
        
          d
          3
        
        =
        
          

        
        ⁢
        
          
        
        ⁢
        
          g
          2
        
      
      ,
      
        
          d
          4
        
        =
        
          c
          3
        
      
      ,
      
        
          
            e
            ^
          
          (
          
            
              d
              1
            
            ,
            
              
                u
                ′
              
              ⁢
              
                
                  ∏
                  
                    i
                    ∈
                    v
                  
                
                ⁢
                
                  
                
                ⁢
                
                  u
                  i
                
              
            
          
          )
        
        =
        
          
            
              
                e
                ^
              
              ⁡
              
                (
                
                  
                    d
                    1
                  
                  ,
                  
                    c
                    ⁢
                    
                      
                    
                    ⁢
                    3
                  
                
                )
              
            
            ⁢
            
              
            
            ⁢
            and
            ⁢
            
              
            
            ⁢
            
              c
              1
            
          
          =
          
            M
            ⁢
            
              
                
                  e
                  ^
                
                ⁡
                
                  (
                  
                    
                      d
                      1
                    
                    ,
                    
                      d
                      2
                    
                  
                  )
                
              
              
                
                  e
                  ^
                
                ⁡
                
                  (
                  
                    
                      d
                      3
                    
                    ,
                    
                      d
                      4
                    
                  
                  )
                
              
            
          
        
      
      ,
      
        
          return
          ⁢
          
            
          
          ⁢
          
            1
            ⁢
            
              

            
            ⁢
            
              
            
            ⁢
            
              (*
              ⁢
              *)
            
            .
            
              
            
            ⁢
            Else
          
          ⁢
          
            
          
          ⁢
          if
          ⁢
          
            
          
          ⁢
          
            d
            1
          
        
        =
        
          sk
          1
        
      
      ,
      
        
          d
          2
        
        =
        
          c
          2
        
      
      ,
      
        
          d
          3
        
        =
        
          sk
          21
        
      
      ,
      
        
          d
          4
        
        =
        
          c
          3
        
      
      ,
      
        
          
            e
            ^
          
          ⁡
          
            (
            
              
                sk
                1
              
              ,
              g
            
            )
          
        
        =
        
          
            
              e
              ^
            
            ⁡
            
              (
              
                
                  g
                  2
                
                ,
                
                  g
                  1
                
              
              )
            
          
          ·
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              e
              ^
            
            (
            
              
                
                  u
                  ′
                
                ⁢
                
                  
                    ∏
                    
                      i
                      ∈
                      v
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    u
                    i
                  
                
              
              ,
              
                sk
                2
              
            
            )
          
        
      
      ,
      
        
          and
          ⁢
          
            
          
          ⁢
          
            c
            1
          
        
        =
        
          M
          ⁢
          
            
              
                e
                ^
              
              ⁡
              
                (
                
                  
                    d
                    1
                  
                  ,
                  
                    d
                    2
                  
                
                )
              
            
            
              
                e
                ^
              
              ⁡
              
                (
                
                  
                    d
                    3
                  
                  ,
                  
                    d
                    4
                  
                
                )
              
            
          
        
      
      ,
    
    ⁢
    
      
    
  



    
    
         return 1. Otherwise, return 0.

(**): The check will pass because:

    
    






  
    
      
        
          
            c
            1
          
          ⁢
          
            
              
                e
                ^
              
              ⁡
              
                (
                
                  
                    d
                    1
                  
                  ,
                  
                    d
                    2
                  
                
                )
              
            
            
              
                e
                ^
              
              ⁡
              
                (
                
                  
                    d
                    3
                  
                  ,
                  
                    d
                    4
                  
                
                )
              
            
          
        
        =
        
        ⁢
        
          m
          ⁢
          
            
              
                e
                ^
              
              (
              
                
                  g
                  2
                  t
                
                ,
                
                  
                    g
                    1
                  
                  (
                  
                    
                      u
                      ′
                    
                    ⁢
                    
                      
                        ∏
                        
                          i
                          ∈
                          v
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        u
                        i
                      
                    
                  
                  )
                
              
              )
            
            
              
                e
                ^
              
              (
              
                
                  g
                  2
                
                ,
                
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                  t
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          m
          ⁢
          
            
              
                
                  e
                  ^
                
                (
                
                  
                    g
                    2
                    t
                  
                  ,
                  
                    g
                    1
                  
                
                )
              
              ·
              
                
                  e
                  ^
                
                (
                
                  
                    g
                    2
                    t
                  
                  ,
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                
                )
              
            
            
              
                e
                ^
              
              (
              
                
                  g
                  2
                
                ,
                
                  
                    (
                    
                      
                        u
                        ′
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            ∈
                            v
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          u
                          i
                        
                      
                    
                    )
                  
                  t
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          m
          ·
          
            
              e
              ^
            
            ⁡
            
              (
              
                
                  g
                  2
                  t
                
                ,
                
                  g
                  1
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          c
          1
        
      
    
  




Similar to the first implementation, the proof of One-wayness can be reduced to semantic security of Waters' IBE scheme. Soundness also holds since a valid c ε C can always be decrypted to a message m for a given skid.
<Embodiment 6> Generic Construction of Time Capsule Signature:
An example forward looking a time capsule signature scheme based on a new primitive, identity-based trapdoor relation (IDTR) as defined in the embodiment 3. Let (Set, Sig, Verify) be the key generation, signature generation and verification algorithms of an ordinary signature scheme, and (Gen, Sample, Extract, Invert, Check) be the tuples of IDTR.

    
    
        1. TSSetup: Let k ε  be a security parameter. The Time Sever gets ()←Gen(1k) and sets public/secret time release key pair (tpk, tsk)=().
        2. UserSetup: Each user runs (pk, sk)←Set(1k) and sets (upk, usk)=(pk, sk).
        3. TSig: To generate a time capsule signature on a message m for a future time t, the signer gets a commitment/witness pair (c, d)←(t), and then computes s←Sigusk(m ∥ c ∥ t). The time capsule signature σ′t is (s, c). The signer stores the sampled witness d.
        4. TVer: A verifier checks if σ′t=( s, c) is a valid time capsule signature by checking whether c ε £Rt and s is a valid standard signature under public key upk, that is, check if Verifyupk (m ∥ c ∥ t)=1. If both are correct, output 1; otherwise, output 0.
        5. TRelease: At the beginning of each time period T, the Time Server gets tdRT←Extracttsk (T) and publishes tdRT as ZT.
        6. Hatch: To hatch a time capsule signature σ′t=(s, c), a party computes {tilde over (d)}←InverttdRt(c). The hatched signature is σt=(s, c, {circumflex over (d)}).
        7. PreHatch: To prehatch a valid time capsule signature σ′t=(s, c), the signer retrieves stored value d, and sets the prehatched signature to σt=(s, c, d). However, if Tver(m, σt, upk, tpk, t)=0, then the algorithm outputs ⊥.
        8. Ver: For a given prehatched (or hatched) signature σt=(s, c, d), the verifier checks the validity of (c, d) by running Checktpk,t(c, d). Then, it verifies s on m ∥ c ∥ t by running Verifyupk ( m ∥ c ∥ t, s). If both verifications are correct, output 1; otherwise, output 0.
    
    


<Embodiment 7> Security Analysis:
The proposed time capsule signature scheme is secure if the underlying public key signature scheme is existentially unforgeable against adaptive chosen message attacks and the IDTR has the properties of one-wayness and soundness. The security of the proposed time capsule signature scheme against Game I, Game II and Game III is proven as below.
Security Against Game I: 1 wins the game if he can generate a valid time capsule signature σ′t=(s, c) such that c ε £Rt, and Verupk(m ∥ c ∥ t, s)=1. Moreover, no party can obtain a witness {hacek over (d)}=InverttdRt(c) such that Checktpk,t(c, {hacek over (d)})=1, where tdRt←Extracttsk (t) is released by the Time Server. This contradicts the Soundness property of IDTR. Thus, the proposed time capsule signature.
Security Against Game II: An adversary B is constructed, which breaks the One-wayness of IDTR with non-negligible advantage if II forges a valid signature σ. Let (m*, t*, σ*) be a successful forgery generated by II. Since the underlying standard signature scheme (Set, Sig,Verify) is euf-cma, II has overwhelming probability to have obtained the corresponding time capsule signature σ′* from oracle TSig rather than forging σ′ on its own.
The game between the IDTR One-wayness challenger and adversary B starts when the challenger generates  and  by running Gen(1k). After receiving  from the challenger, B interacts with II in Game II as follows:
B gets a random public/private key pair (pk, sk)←Set(1k), sets (upk, usk)=(pk, sk), tpk, =, and gives (tpk, upk) to II.
B manages a list L={(mi, ti, si, ci, di)} for answering II's queries on PreHatch. Let qTSig be the total number of TSig queries made by II and r be the random number chosen by B in the interval of [1, qTSig]. B responds to the i-th TSig query (mi, ti) as follows:

    
    
        If i=r, B sends tr to the IDTR One-wayness challenger and receives a random commitment c ε Rtr from the challenger. B sets cr=c and computes sr=Sigusk(mr ∥ cr ∥ tr). B returns σ′tr=(Sr, Cr) to II and stores (mr, tr, sr, cr, ⊥) in the list L.
        If i≠r, B gets a random commitment/witness pair (ci, di) generated from  and computes si=Sigusk(mi ∥ ci∥ ti). B returns σ′ti=(si, ci) to II and stores (mi, ti, si, ci, di) in L.
    
    


To simulate oracle TRelease, say on query ti from II, B relays ti to the trapdoor extraction oracle Extract simulated by the IDTR One-wayness challenger and gets tdRti. If ti=tr, B aborts. Otherwise, B returns zti=toti to II.
To simulate oracle PreHatch, say on query (mi, ti, si, ci) , B checks whether the query is in the list L or not. If (mi, ti, si, ci) is in the list L, and equal to (mr, tr, sr, cr), B aborts. If (mi, ti, si, ci) is in the list L, and not equal to (mr, tr, sr, cr), B extracts di from L and gives a prehatched signature σti=(si, ci, di) to II. If (mi, ti, si, ci) is not in L, since II does not know usk and this case implies that si is not generated by B on mi ∥ ci ∥ ti, due to the euf-cma assumption of the underlying standard signature, it is negligible to have si be valid. Hence this case will happen with negligible chance. Therefore, for this case, B returns ⊥.
When II outputs the forgery (m*, t*, σ*) where σ*=(s*, C*, d*), B verifies whether the forgery passes the verification algorithm Ver, and (m*, t*, s*, c*)=(mr, tr, sr, cr). If so, B outputs the witness d*. Otherwise, it chooses a dB randomly and outputs dB. The probability that B does not abort during the simulation and has a right guess of r is at least 1/qTSig since r is randomly chosen. Therefore, if II forges with a probability ε, B succeeds in breaking the One-wayness of IDTR with probability ε≧ε/qTSig.
Security Against Game III: To show the security against Game III, we convert any adversary III, which wins in Game III to a forger F against the underlying standard signature scheme. F gets pk as an input, and has access to signing oracle Sig of the signature scheme as described in the euf-cma model [16]. F simulates Game III for III as follows:
F gets ()←Gen(1k) and gives (upk, tpk, tsk)=(pk, ) to III. F simulates TSig on query (mi, ti) by getting (ci, di)←(ti) and obtaining si←Sig (mi∥ ci ∥ ti) from signing oracle Sig. F stores (mi, ci, di, ti) in a list L={(mi, ci, di, ti)} for answering III's queries to PreHatch. To simulate PreHatch on query (mi, ti, si, ci), F verifies if si is a valid signature on mi ∥ c ∥ ti.

    
    
        If si is valid, F checks if (mi,ci,ti) is in the list L. If so, F gives the corresponding di to III. Otherwise, si is a new signature value and F succeeds in producing a new forgery si on mi ∥ ci ∥ ti.
        If si is not valid, F returns ⊥ due to the same reason as shown above in the Security Against Game II.
    
    


Finally, when III outputs a forgery (m*, t*, σt*) where σt*=(s*, c*, d*), F outputs a signature s* on message m* ∥ c* ∥ t*. Therefore, if III succeeds with a probability ε, F succeeds in producing a new forgery with at least probability ε.
<Embodiment 8> Extended IDTR:
Ahe extended IDTR has seven PPT algorithms including: Gen, Sample, Reveal, Extract, Invert, CheckS and CheckI. The settings of Gen, Sample, Extract and Invert remain the same as in IDTR. Reveal is used to print out a “sampled” witness. Check in IDTR is replaced by two separated functions: CheckS and CheckI, which are used to check the validity of the sampled witness value d and inverted witness value {circumflex over (d)}, respectively. The definition of these newly added algorithms (Reveal, CheckS and CheckI) are showed as follows:

    
    
        Reveal: Given c ε £Rid, if there is a pair (c, d) in a sampling list defined by List={(c, d, id)} where (c, d)←(id), Revealid(c) returns witness d. Otherwise, it returns ⊥.
        CheckS: For any (c, d)←(id), we have (c, d) return 1 (accept); otherwise, it returns 0 (reject).
        CheckI: Given (c,{circumflex over (d)}) ε Rid, where {tilde over (d)}←(c), (c,{circumflex over (d)}) returns 1 (accept). Otherwise, it returns 0 (reject).
    
    


With this modification, the extended IDTR can be used to achieve another property called Hiding, which is beyond One-wayness and Soundness. Hiding captures a malicious system master (e.g. a malicious Time Server) who aims to forge a sampled witness for a given commitment.

    
    
        Hiding: Let Osample and OReveal be oracles simulating the procedures of Sample and Reveal, respectively, where Osample only returns a commitment for each query. Let Query(A, OX) be the set of queries an algorithm A asked to OX, where X can be Sample or Reveal. Note that A can only obtain commitment c from Osample. It states that the following probability is negligible for all PPT algorithm A:
    
    






  Pr
  ⁡
  
    [
    
      
        
          
            Check
            
              
                D
                R
              
              ,
              
                id
                *
              
            
          
          ⁡
          
            (
            
              
                c
                *
              
              ,
              
                d
                *
              
            
            )
          
        
        =
        
          
            
              1
              ⋀
              
                c
                *
              
            
            ∈
            
              
                Query
                ⁡
                
                  (
                  
                    A
                    ,
                    
                      O
                      sample
                    
                  
                  )
                
              
              ⋀
              
                c
                *
              
            
            ∉
            
              Query
              ⁡
              
                (
                
                  A
                  ,
                  
                    O
                    Reveal
                  
                
                )
              
            
          
          |
          
            
              (
              
                
                  D
                  R
                
                ,
                
                  mtd
                  R
                
              
              )
            
            ←
            
              Gen
              ⁡
              
                (
                
                  1
                  k
                
                )
              
            
          
        
      
      ;
      
        
          (
          
            
              c
              *
            
            ,
            
              d
              *
            
            ,
            
              id
              *
            
          
          )
        
        ←
        
          
            A
            
              
                O
                sample
              
              ⁢
              
                O
                Reveal
              
            
          
          ⁡
          
            (
            
              
                D
                R
              
              ,
              
                mtd
                R
              
            
            )
          
        
      
    
    ]
  




<Embodiment 9> A Generic construction of Extended IDTR:
Let ε be an IBE scheme. Let ε.Enc(mpk, id, m; r) be ε's encryption algorithm which encrypts message m under identity id and master public key mpk using randomness r. We say that ε is injective if it satisfies the following condition:
Injective: For every master public key mpk and every identity id, for every ciphertext e of a message m under mpk and id, there exists at most one randomness r such that e=ε.Enc(mpk,id,m;r).
In the literature, many IBE schemes are injective, like Basicldent and Fullldent proposed by Boneh and Franklin, and Waters' IBE.
Suppose ε=(Setup, Extract, Enc, Dec) is an injective encryption scheme with IND-ID-CPA security, MSP is the message space, and RSP is the space of randomness used in ε.Enc. Let f:{0,1}l(k)→RSP be a one-way function (or a hash function). We now give a generic construction of extended IDTR as follows.

    
    
        Gen: On input 1k, run ε.Setup (1k) to generate a master key pair (mpk, msk) and set =mpk and =msk.
        Sample: On input  and id , randomly select m ε MSP and s ε {0,1}l(k), compute r=f(s), and run ε. Enc (, id, m; r) to generate a ciphertext e of m under the identity id. Store (id, c, d)=(id, (e), (m, s)) into a sampling list List and return (c, d).
        Extract: Given  and id, run ε.Extract(, id) to generate the corresponding private key skid with respect to the identity id, and return =skid.
        Invert: Given  and c, run ε.Dec(, , c) to get the plaintext m, and return {circumflex over (d)}=(,m).
        Reveal: Given c ε £Rid, check if there is an entry for c in the sampling list List={(id, c, d)}. If so, return the corresponding d; otherwise return ⊥.
        CheckS: For any pair (c, d) output by algorithm Sample on input  and id, we have that (c,d)=((e),(m,s)). Check if ε.Enc(,id,m;f(s))=e. If so, return 1 (accept); otherwise return 0 (reject).
        CheckI: For any (c,{circumflex over (d)}) ε Rid, where {circumflex over (d)}← (c), we have that (c,{circumflex over (d)})=((e),(skid,m)). Check if m=ε.Dec(, skid,e). If so, return 1 (accept); otherwise, return 0 (reject).
    
    


The above scheme is a secure extended IDTR scheme, provided that the underlying IBE scheme ε is IND-ID-CPA secure, and function f is one-way. For the sake of completeness of underlying ID-based Encryption schemes, we provide all the proofs of One-wayness, Soundness and Hiding here.
One-wayness: If the above scheme is not one-way, namely, there is a PPT algorithm =(1, 2) which breaks the one-wayness property with non-negligible probability ε, we then construct a PPT algorithm B to break the IND-ID-CPA-security of the underlying encryption scheme ε with non-negligible probability as well.
After obtaining system parameters and master public key mpk from its challenger, B sets =mpk and runs  on input DR. To answer 1's Extract query on id, B forwards this query to its own Extract oracle, and forwards the answer skid as tdRid back to . After 1's Extract query phase is over, B randomly selects an id* which was not queried by 1, along with two random messages m0, m1ε MSP. It sends id*, m0, m1 to its own challenger. After receiving a ciphertext e* of either m0 or m1, B sets c=(e*), and feeds (id*, c) to 2. Again, B needs answer 2's Extract queries. It acts the same as in answering 1's Extract queries with the only exception that if the query input id is equal to id*, B aborts the simulation and outputs a random bit.
Finally, 2 outputs a {circumflex over (d)}=({circumflex over (d)}1, {circumflex over (d)}2). Then B computes b0=(c, {circumflex over (d)}) and b0=(c, {circumflex over (d)}). If b0=1, B could easily get the corresponding private key skid* of identity id* as well as the plaintext m′ of e*, such that m′=ε.Dec(mpk, skid*, e*). It's guaranteed by the correctness of ε that m′ must be either m0 or m1. Thus, B can output the right bit b. Otherwise, if b1=1, we have that e*=ε.Enc(mpk, id*, {circumflex over (d)}1;f ({circumflex over (d)}2)). Again, guaranteed by the correctness of ε, {tilde over (d)}1, is either m0 or m1. Thus B can know a bit b such that mb={circumflex over (d)}1. It outputs b and wins in the IND-ID-CPA game. If both b0 and b1 are 0, B simply flips a coin, and outputs the outcome. Obliviously, if  succeeds, B also succeeds. Therefore, the probability that B wins in the IND-ID-CPA game is at least




  
    
      ε
      +
      
        
          1
          2
        
        ⁢
        
          (
          
            1
            -
            ε
          
          )
        
      
    
    =
    
      
        1
        2
      
      +
      
        
          1
          2
        
        ⁢
        ε
      
    
  
  ,




which is non-negligibly greater than one-half.

Soundness: The soundness is guaranteed by the correctness of the underlying encryption scheme ε. That is, for any valid ciphertext e with respect to any identity id, the owner of the corresponding private key skid can always decrypt e to the original message m.
Hiding: If the above scheme is not hiding, that is, there is a PPT algorithm  which can break the hiding property with non-negligible probability ε, then we can construct another PPT algorithm B to break the one-wayness of function ƒ with non-negligible probability as well.
On input y=ƒ(x) for some string x ε {0,1}l(k), B runs  as a subroutine. Suppose that  issues at most qS queries to OSample and at most qR queries to OReveal. Implicitly, we have that qS>qR. B randomly chooses i ε {1,2, . . . , qS}, and then simulates oracles OExtract and OReveal for  as follows:

    
    
        OSample: Suppose that this is the j-th query. On input idj, B randomly selects m ε MSP. If j=i, B sets r=y and d=(m, ⊥); otherwise, B randomly selects S ε {0,1}l(k), computes r=ƒ(s) and set d=(m,s). It computes e ←ε.Enc(, idj, m; r) and sets c=(e). B stores (idj, c, d) into a sampling list List, and returns c. Note that in this way B perfectly simulates Osample's answers.
        OReveal: On input id and c=(e), B searches its sampling list List for an entry for (id, c). If there is no List or no such an entry (id,c,d=(d1,d2)), B returns ⊥; otherwise, if d2=⊥, B aborts; otherwise, it returns d.
    
    


Finally,  outputs (id*, (c*, d*)) where d*=(d1*, d2*). If  wins in the Hiding game, we have c* ε Query(, OSample), c* ∉ Query(, OReveal) and (c*, d*)=1. It implies that c*=ε.Enc(,id*, d1*,ƒ(d2*)). If B's guess is correct, namely, c* is returned in the answer to the i-th Sample query, then by the injective property of E, we have that ƒ(d2*)=y. Thus, d2* is a pre-image of y. The probability that B succeeds in guessing i is at least 1/qs. If  breaks the Hiding property with probability ε, then B breaks the one-wayness of ƒ with probability at least ε/qs, which is non-negligible. This is a contradiction to the one-wayness of ƒ.
<Embodiment 10> Extended Time Capsule Signature:
Based on the extended IDTR, the Ver function in time capsule signature can also be separated into two functions accordingly: VerP is to verify the prehatched signature, and VerH is to verify the hatched signature. The generic construction of time capsule signature based on IDTR can then be modified as follows:

    
    
        VerP: For a given prehatched signature σt=(s, c, d) on m, a verifier checks if CheckStpk,t(c, d) outputs 1 and Verifyupk(m∥c∥t,s) outputs 1. If both of the verifications are correct, output 1; otherwise, output 0.
        VerH: For a given hatched signaturesσt=(s, c, {circumflex over (d)}) on m, the verifier compares the current time with t. If the current time is smaller than t, it returns ⊥ indicating that hatching cannot be done at the moment. Otherwise, the verifier determines if CheckItpk,t(c, {circumflex over (d)}) outputs 1 and Verifyupk(m∥c∥t, s) outputs 1. If both of the verifications are correct, output 1; otherwise, output 0.
    
    


The Time Server should be fully trusted and it is assumed that the Time Server would not collude with any malicious user and release some time trapdoor zt before t. Otherwise, there is no way to distinguish whether a signature is pre-hatched by the actual signer or hatched by a malicious Time Server. In the distinguishable time capsule signature, the act of a malicious Time Server is distinguishable. Below is the formal security model. Let k ε  be a security parameter.
Game IV: Let SIV be the game simulator.

    
    
        1. SIV executes TSSetup(1k) to get (tpk, tsk) and UserSetup(1k) to get (upk, usk).
        2. SIV runs IV on upk, tpk and tsk. During the simulation, IV can make queries onto TSig, and PreHatch.
        3. IV is to output (m*, t*, σ*).
        IV wins if VerP(m*, σ*, upk, tpk, t*)=1, and IV has never queried PreHatch(m*, t*,·).
    
    


A time capsule signature scheme is secure in Game IV if for all PPT algorithm IV, it is negligible for IV to win the game. Now the security of our proposed time capsule signature scheme against Game IV is proven.
The extended time capsule signature scheme is secure in Game IV if the underlying extended IDTR scheme has the Hiding property, and the standard signature scheme is existentially unforgeable against adaptive chosen message attacks.
To show security against Game IV, we construct an adversary B which can compromise Hiding of the extended TDTR with non-negligible advantage if IV can non-negligibly forge a prehatched signature σ*. Let (m*, t*, σ*) be a successful forgery by IV, where σ*=(s*, c*, d*). Note that it has overwhelming probability that IV obtained the corresponding time capsule signature σ′* from oracle TSig. This is because of the euf-cma assumption of the underlying standard signature scheme.
The game between the challenger of the extended IDTR Hiding game and adversary B starts when the challenger generates  and  by running Gen(1k), and then gives  and  to B. B then interacts with IV as follows:
B gets a random public/private key pair (pk, sk)←(Set(1k), sets (upk, usk)=(pk, sk), (tpk, tsk)=(), and gives (tpk, tsk, upk) to IV.
B manages a list L={(mi, ti, si, ci, di)} for answering IV's queries to PreHatch. Let qTSig and qPreH be the total number of TSig and PreHatch queries made by IV, respectively, and r be the random number chosen by B in the interval of [1, qTsig]. B responds to the i-th TSig query (mi, ti) as follows:

    
    
        If i=r, B queries to its challenger on the Sample oracle on tr and receives a random commitment c ε Rtr. B sets cr=c and computes sr=Signsk(mi ∥ ci ∥ ti). B returns σ′tr=(sr, cr) to IV and stores (mr, tr, sr, cr, ⊥) in L.
        If ≠r, B gets a random commitment/witness pair (ci, di)← and si←(mi ∥ ci ∥ ti). B returns σ′ti=(si, ci) to IV and stores (mi, ti, si, ci, di) in L.
    
    


To simulate PreHatch on query (mi, ti, si, ci) , B checks if the query is in the list L. If (mi, ti, si, ci) is L, and equal to (mr, tr, sr, cr), B aborts. If (mi, ti, si, ci) is in L, and not equal to (mr, tr, sr, crr), B obtains di from L and gives a prehatched signature σti=(si, ci, di) to IV. If (mi, ti, si, ci) is not in L, since IV does not know usk and this case implies that si is not generated by B on mi ∥ ci ∥ ti, due to the euf-cma assumption of the underlying standard signature scheme, it is negligible to have si be valid. Hence this case will happen with negligible chance. For this case, B returns ⊥.
When IV outputs the forgery (m*, t*, σ*) where σ*=(s*, c*, d*), B determines if the forgery passes CheckS, and (m*, t*, s*, c*)=(mr, tr, sr, cr). If so, B outputs di. Otherwise, it chooses a value d randomly and outputs d. The probability that B does not abort during the simulation and has the right guess of r is at least 1=qTSig since r is randomly chosen (*). Therefore, if IV forges with success probability at least ε, B succeeds in breaking the Hiding property of the extended IDTR with probability at least ε/qTSig.
(*) Without loss of generality, we assume that each TSig query is distinct and each PreHatch is also distinct, and qPerH≦qTSig. The probability that IV outputs a forgery (m*, t*, s*, c*) which passes CheckS but not in the list L is negligible due to the euf-cma assumption of the underlying standard signature scheme. B does not abort when answering the first PreHatch query is at least (1−1/qTSig). It does not abort when answering the second PreHatch query is at least (1−1/qTSig)×(1−1/(qTSig−1)). Finally we get




  
    
      Pr
      ⁡
      
        [
        
          B
          ⁢
          
            
          
          ⁢
          does
          ⁢
          
            
              
            
            ⁢
            
              
            
          
          ⁢
          not
          ⁢
          
            
          
          ⁢
          abort
        
        ]
      
    
    ≥
    
      
        (
        
          1
          -
          
            1
            
              q
              TSig
            
          
        
        )
      
      ×
      
        (
        
          1
          -
          
            1
            
              
                q
                TSig
              
              -
              1
            
          
        
        )
      
      ×
      ...
      ×
      
        (
        
          1
          -
          
            1
            
              
                q
                TSig
              
              -
              
                g
                PerH
              
              +
              1
            
          
        
        )
      
    
  
  =
  
    
      
        
          
            q
            TSig
          
          -
          1
        
        
          q
          TSig
        
      
      ×
      
        
          
            q
            TSig
          
          -
          2
        
        
          
            q
            TSig
          
          -
          1
        
      
      ×
      ...
      ×
      
        
          
            q
            TSig
          
          -
          
            q
            PerH
          
        
        
          
            q
            TSig
          
          -
          
            q
            PerH
          
          +
          1
        
      
    
    =
    
      
        
          q
          TSig
        
        -
        
          q
          PerH
        
      
      
        q
        TSig
      
    
  




And B makes the right guess of r in the remaining qTSig−qPerH tuples is 1/(qTsig−qPerH). Thus, the probability that B does not abort during the simulation and makes the right guess of r is at least 1/qTSig.
What has been described above includes examples of the subject innovation. It is, of course, not possible to describe every conceivable combination of components or methodologies for purposes of describing the subject innovation, but one of ordinary skill in the art can recognize that many further combinations and permutations of the subject innovation are possible. Accordingly, the disclosed subject matter is intended to embrace all such alterations, modifications and variations that fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term “includes” is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term “comprising” as “comprising” is interpreted when employed as a transitional word in a claim.
Inference can also refer to techniques employed for composing higher-level events from a set of events and/or data. Such inference results in the construction of new events or actions from a set of observed events and/or stored event data, whether or not the events are correlated in close temporal proximity, and whether the events and data come from one or several event and data sources. Various classification schemes and/or systems (e.g., support vector machines, neural networks, expert systems, Bayesian belief networks, fuzzy logic, data fusion engines) can be employed in connection with performing automatic and/or inferred action in connection with the disclosed subject matter.
Some portions of the detailed description have been presented in terms of algorithms and/or symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and/or representations are the means employed by those cognizant in the art to most effectively convey the substance of their work to others equally skilled. An algorithm is here, generally, conceived to be a self-consistent sequence of acts leading to a desired result. The acts are those requiring physical manipulations of physical quantities. Typically, though not necessarily, these quantities take the form of electrical and/or magnetic signals capable of being stored, transferred, combined, compared, and/or otherwise manipulated.
The above description of illustrated embodiments of the invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes, various modifications are possible within the scope of the invention, as those skilled in the relevant art should recognize.
These modifications can be made to the invention in light of the above detailed description. The terms used in the following claims should not be construed to limit the invention to the specific embodiments disclosed in the specification. Rather, the scope of the invention is to be determined entirely by the following claims, which are to be construed in accordance with established doctrines of claim interpretation.

## Claims

1. A method for validation in an e-commerce transaction, comprising:
receiving, by a second device comprising a processor and a memory from a first device comprising another processor and another memory over a network, a time capsule signature for an e-commerce transaction message for a committed time and a sampled witness value based on the committed time generated by the first device, wherein the committed time is based on a trusted time server arbitrating the e-commerce transaction between the first device and the second device;
receiving, by the second device from the first device over the network, a pre-hatched signature for the e-commerce transaction message based upon the time capsule signature and the sampled witness value generated by the first device using a first algorithm; and
validating, by the second device, the e-commerce transaction message using the pre-hatched signature before the committed time, comprising:
generating, by the second device, a hatched signature for the e-commerce transaction message based on the time capsule signature and the sampled witness value using a second algorithm, wherein the pre-hatched signature and the hatched signature are distinguishable from each other; and
identifying, by the second device, that a time of validating the e-commerce transaction message using the pre-hatched signature is prior to the committed time based on the prehatched signature and the hatched signature being distinguishable from each other.

2. The method of claim 1, further comprising: setting, at the trusted time server, a first public key and a first secret key based on a security parameter; and setting, at the first device, a second public key and second secret key based on the security parameter.

3. The method of claim 2, wherein the first public key comprises a description of a trapdoor relation, and the first secret key comprises a master trapdoor for extracting a trapdoor of the trapdoor relation.

4. The method of claim 2, wherein the security parameter is determined by a binary length of key material.

5. A method for validation in an e-commerce transaction, comprising:
generating, by a first device comprising a processor, a time capsule signature on an e-commerce transaction message for a committed time and a sampled witness value based on the committed time, wherein the sampled witness value is stored in a memory of the first device and the first device does not require information from other devices to access the sampled witness value
transmitting, by the first device, over a network to a second device comprising another processor and another memory, the time capsule signature for the e-commerce transaction message for the committed time and the sampled witness value based on the committed time generated by the first device, wherein the committed time is based on a trusted time server arbitrating the e-commerce transaction between the first device and the second device;
generating, by the first device, a pre-hatched signature transmitted over the network to the second device for the e-commerce transaction message by relating the time capsule signature and the sampled witness value, wherein the pre-hatched signature and a hatched signature for the e-commerce transaction message based on the time capsule signature and the sampled witness value are distinguishable from each other, and wherein a time of validating the e-commerce transaction message using the pre-hatched signature prior to the committed time is identifiable based on the pre-hatched signature and the hatched signature being distinguishable from each other;
transmitting, by the first device, over the network to the second device the pre-hatched signature.

6. A method for validation in an e-commerce transaction, comprising:
validating, by a second device comprising a processor and a memory, an e-commerce transaction message using a pre-hatched signature generated at a first device comprising another processor and another memory based on a time capsule signature and a sampled witness value, wherein the pre-hatched signature is validated before a committed time, and the first device is coupled to the second device via network over which the e-commerce transaction message and pre-hatched signature are communicated from the first device, wherein the committed time is based on a trusted time server arbitrating the e-commerce transaction between the first device and the second device;
wherein the validating comprises:
generating, by the second device, a hatched signature based on the time capsule signature and the sampled witness value generated at the first device, wherein the pre-hatched signature and the hatched signature are distinguishable from each other; and
identifying, by the second device, that a time of validating the message using the pre-hatched signature is prior to the committed time based on the prehatched signature and the hatched signature being distinguishable from each other.

7. The method of claim 6, further comprising receiving, by the second device, the sample witness value.

8. The method of claim 7, further comprising checking, by the second device, the sample witness value using a first function.

9. The method of claim 8, further comprising, receiving, by the second device, the inverted witness value.

10. The method of claim 9, further comprising checking, by the second device, the inverted witness value using a second function.

11. The method of claim 2, wherein the first public key is a public time release key, the first secret key is a secret time release key, the second public key is a user public key, and the second secret key is a user secret key.

12. The method of claim 3, further comprising generating, by the first device, an inverted witness value based on the description of the trapdoor relation and the committed time.

13. The method of claim 12, further comprising checking, by the second device, the sample witness value using a first function.

14. The method of claim 13, further comprising checking, by the second device, the inverted witness value using a second function.

15. The method of claim 5, further comprising: setting, at the trusted time server, a first public key and a first secret key based on a security parameter; and setting, by the first device, a second public key and second secret key based on the security parameter.

16. The method of claim 15, wherein the first public key comprises a description of a trapdoor relation, and the first secret key comprises a master trapdoor for extraction of a trapdoor of the trapdoor relation.

17. The method of claim 16, further comprising generating, by the first device, an inverted witness value based on the description of the trapdoor relation and the committed time.

18. The method of claim 17, further comprising transmitting, by the first device, the sample witness value to the second device.

19. The method of claim 18, further comprising, transmitting, by the first device, the inverted witness value to the second device.

20. The method of claim 15, wherein the security parameter is determined by a binary length of key material.