Note: Descriptions are shown in the official language in which they were submitted.
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
METHOD AND SYSTEM FOR TRANSIENT KEY DIGITAL TIME STAMPS
FIELD OF THE INVENTION
The present invention relates to a method for digital time
stamping data. More particularly, the present invention
relates to the digital time stamping of data, without the need
for subsequent third party verification, by the chaining of
key pairs, the key pairs being generated for particular time
intervals.
BACKGROUND INFORMATION
The concept of chain of evidence has long been a fundamental
tenet of the U.S. judicial system. Many legal situations
depend upon the ability to prove that a certain piece of
evidence existed at a certain point in time and that it has
not been subsequently altered. In the past, when most of the
possible types of evidence consisted of material objects,
there was a need for a protocol of a"chain of witnesses" to
testify to the veracity of an evidentiary object in question.
Historically, if the evidence was under the control of only a
finite set of individuals, and if all of those individuals
could testify as to the location and state of the object, then
the court would accept the claim of authenticity of the
evidence.
Of course, such a system is dependent upon the availability of
trustworthy witnesses that will be available and willing to
testify in any given circumstance. Often times, witnesses are
available, but not trustworthy, or vice versa. This is
particularly the case with respect to document authentication,
1
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
where the details of when a specific document was created or
signed is in question. Clearly, a system was needed to allow
one to easily obtain a"witness on demand" in many situations.
This concept of evidentiary authentication is so important to
so many areas of endeavor, that a formalized system of
professional document witnesses was developed, for example,
called the Notary Public service. Notary Publics would, for a
fee, attest to such things as the existence of a document and
the identity of the document holder or signer. Of course a
notary could not swear to any knowledge of the actual contents
of a document, since that would have required that the notary
keep copies, in perpetuity, of every document ever witnessed
-- an impractical requirement. Much of the trust held in the
notary public system related to a generally-held belief that
it was impossible or impractical to forge a notary public's
stamp and signature, or to buy a notary public's testimony.
As computer graphics and desktop publishing technology
advances, however, the level of difficulty of creating forged
documents and signatures decreases significantly. A result of
this technological advance is the fact that some states, such
as California, no longer accept notarization as absolute proof
of document validity.
As more and more of the information of import in personal and
business transactions becomes digital in form, the usefulness
of notary-public-style authentication mechanisms decreases.
Much of this information is stored, accessed and managed
through computer database management systems. All major
database systems permit time stamping of data in records.
Many commercial and governmental systems depend upon the
assumption of veracity of such database time stamps. The
presumption is that, if the organization is trustworthy, then
2
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
the time stamps in their databases can be believed. In
practice, this assertion requires a large degree of, to borrow
a literary term, "willing suspension of disbelief." No one,
of course, can safely assume that all individuals within a
large organization are trustworthy, even if the organization,
itself, is believed to be so. Furthermore, it is now well
known that no conventional computer database system is immune
from the possibility of data tampering or "hacking" by
dishonest individuals.
One approach that has been developed to deal with some of this
problem is based upon a technology called "public key"
cryptography. One of the most well known of this type of
system is the program called Pretty Good Privacy, distributed
by the Massachusetts Institute of Technology, which makes use
of the Rivest-Shamir-Adleman (RSA) public key cryptosystem.
Such systems are built around the concept of encrypting data
in such a way that allows both secure transmission and
authentication of sensitive data. Public key systems employ a
pair of cryptographic keys for each encryption/decryption
event. One key is kept secret by the owner (e.g., the private
key), and the other key is publicly distributed (e.g., the
public key). A message encrypted with one of the keys in a
key pair can only be decrypted with the other key, and vice
versa.
This system allows, for example, the encryption of data by one
individual, using a second individual's public key. The
message could then be sent to a second individual over
unsecure channels, and only the second individual could access
the unencrypted data, since it could only be decrypted with
the second individual's private key.
3
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
Prior to using the second individual's public key to encrypt
the data, the first individual could have used his or her
private key to encrypt the data, thereby digitally "signing"
the data. The recipient could then use the sender's public
key to decrypt it, thus proving that it actually came from the
sender, since only the sender could have used the correct
secret key to sign the data. Such a system provides both
confidentiality of data and a mechanism for authentication of
the identity of the sender. It also proves that the data
could not have been altered in any way since the time it was
encrypted by the sender. Public keys, themselves, can be
"certified" by signing them with a trusted individual's secret
key (e.g., a digital signature). Others can then assess the
authenticity of published public keys by authenticating them
using that trusted individual's public key. If that trusted
individual later loses faith in the validity of the certified
key, then he can issue a so-called revocation certificate,
signed by the trusted individual's private key, that notifies
others that the previously-certified public key is no longer
to be trusted in the future.
Public key algorithms are notoriously slow. For this reason,
virtually all public key digital signature systems use what is
called a "cryptographically-strong one-way hash function" to
create what is called a "message digest" from the data to be
signed. This message digest is a unique representation of
that data, sort of a data fingerprint, that is typically much
smaller than the original data. For example, the message
digests that PGP uses are only 128 bits in length. The
message digest is then encrypted using the sender's secret key
before sending the data to the recipient. The recipient can
then use the sender's public key to automatically decrypt the
message digest and then verify that it does indeed match the
original data. This is a very secure system, since it is
4
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
computationally infeasible for an attacker to devise a
substitute message that would provide an identical message
digest. Most estimates state that it would take 10^12 or more
years (taking into account Gordon Moore's "law" relating to
increases in chip capacity over time) to successfully fake a
128-bit message digest using the algorithm employs by the PGP
software package. Also, changing even a single byte of a
digested message would cause the hash function to be unable to
match the message digest to the unencrypted data.
Public key digital signatures, therefore, can irrefutably
prove that signed data was originally signed by a given secret
key and that the data has not changed in any way since the
signature was made. Systems such as PGP routinely attach
time-stamps to both key pairs at their creation, and to
digital signatures, each time they are created. Such time-
stamps, however, are dependent only upon the internal clocks
within the computers being used, and thus are subject to
inaccuracies or falsification by, for example, an individual
intentionally changing the time on a computer's clock in order
to make it falsely appear that a given digital signature was
created at a specific point in time.
For this reason, a new type of notary public has arisen, which
uses public-key digital signatures to notarize, for a fee,
digital information typically submitted over the Internet.
These so-called "digital notaries" are, essentially,
businesses that provide such a service and agree to attest to
the veracity of both the content of the original data, as well
as the time at which the signature was made. This is a major
improvement over the notary public concept of old, since the
new digital notary services can testify to the fact that data
which has been digitally signed by their service existed at a
5
CA 02304342 2000-11-23
certain point in t;.me, and that: it hasn't been altered in any
way since that point in time. The largest problem with such
digital notary services, and also a motivating reason for the
method according to the present invention, is the fact that
the authenticity of such digital-nor_ary-generated digital
signatures is wholly dependent upon the trustworthiness of the
institution and individuals running the digital notary
service.
To solve this problem, a systein is needed that will
automatically and rigo:r-ous:.y prove the veracity of diai:.al
signature time-stamps, wi.thout depending upon the
trustworthiness of the institution or individuals
administering a digital rlotary service. -irans.ient-key digital
time-stamps according to an embodiment of the present
invention provide these capabilities.
6
CA 02304342 2000-11-23
SUMbIARY OF THE INVENTION
An object of the present invention is to provide a method and
system for transient key digital time stamps. In accordance
with an aspect of the present invention, there is provided a
method for certifying datei, comprisirig the steps of: generating
a key p'air at a first time interval, the key pair including a
private key and a public key; receiving a certification request;
automatically responding t:o the certification request by
digitally signing data associated with the certification request
using the private key; and deleting the private key.
In accordance with another aspect of the invention, there is
provided a method for cert:_Lfying data, comprising the steps of:
generating a first key pa_Lr at a first time interval, the first
key pair including a first public key and a first private key;
generating a second key pair at a second time interval, the
second key pair including a second public key and a second
private key; signing the second publ:i.c key using the first
private key; deleting the first private key; processing a
certification request d.ur_Lng the second time interval using the
second private key; and dE=_leting the second private key.
In accordance with another aspect of the invention, there is
provided a system for certifying data, comprising: a general
purpose computer; and an. I/O device coupled to the general
purpose computer, wherein the general purpose computer includes
a memory containing a pr.ogram executable by the general purpose
computer, the executable program instructing the general purpose
computer to: generate a key pair at a first time interval, the
6a
CA 02304342 2000-11-23
key pair including a private key and a public key; receive a
certification request; automatically respond to the
certification request by digitally signing data associated with
the certification request using the private key; and delete the
private key.
In accordance with another aspect of the invention, there is
provided a system for certifying data, comprising: a general
purpose computer; and an I/O device coupled to the general
purpose computer, where:in the general purpose computer includes
a memory containing a pragram executable by the general purpose
computer, the executable program instructing the general purpose
computer to: generate a first key pair at a first time interval,
the first key pair including a first public key and a first
private key; generate a second key pair at a second time
interval, the second key pair including a second public key and
a second private key; sign the second public key using the first
private key; delete the first private key; process a
certification request during the second time interval using the
second private key; and delete the second private key.
According to an embodiment of the present invention,
irrefutable public key digital signature time-stamps are
created and used. The sys_em is based upon, for example, the
2- concept of transient t.Lme- interval-- related secret
cryptographic: keys, whic:h are used to digitaliy sign submitted
data during specific time intervals, and then are permanently
destroyed. The pubiic-key correlate for each time interval is
saved for future authentication of the content of time-stamped
3() data and time of creation of time-::tamped data. The validity
of the public keys is ensured through the certification (e.g.,
signing) of each time interval's public key using the p_-evious
time interval's secret key, immediately before that secret kev
is destroyed.
6b
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 illustrates an exemplary flowchart for a method for
digital time stamping according to an embodiment of the
present invention.
Figure 2A illustrates a portion of an exemplary flowchart for
another method for digital time stamping according to an
embodiment of the present invention.
Figure 2B illustrates another portion of an exemplary
flowchart for another method for digital time stamping
according to an embodiment of the present invention.
Figure 3A illustrates a first exemplary embodiment for a time
stamping system according to the present invention.
Figure 3B illustrates a second exemplary embodiment for a time
stamping system according to the present invention.
DETAILED DESCRIPTION OF THE INVENTION
The digital time stamping method according to an embodiment of
the present invention provides a mechanism to irrefutably
prove that a collection of data existed at a given interval of
time and has not changed since that interval of time. A
significant advantage of the present invention is that it
provides non-repudiation to the user. It is difficult to deny
the veracity of the time-stamp certificates generated by the
method according to an embodiment of the present invention.
For example, the system does not depend upon the
trustworthiness (or later existence) of any external
7
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
"certification authority" or any external time tracking
system. Rather, all that is needed to authenticate the time
stamp generated according to an embodiment of the present
invention is, for example, the time-stamped data, the
signature from the time-stamp certificate, the time interval's
public key from the time-stamp certificate, and a standard
public-key authentication program, such as either the free or
commercial version of PGP. Other public key encryption
programs such as the J/CRYPTO Professional Cryptography
Classes for Java Developers
(http://www.baltimore.ie/products/jcrypto/index.html) could
also be used with the present invention. Moreover, the method
according to an embodiment of the present invention will work
with any kind of computer data.
Systems utilizing the method for transient-key digital time
stamps according to the present invention can be set up as,
for example, Internet servers, stamping all requests on a fee-
for-service basis. The time of creation and the internal
state of information can be proven without endangering the
confidentiality of sensitive data. The time stamping method
according to an embodiment of the present invention makes the
method suitable for use in, for example, invention
documentation systems. Accordingly, the method according to
an embodiment of the present invention can also be used to
authenticate critical confidential records, such as medical
records and financial transactions, can be easily adapted to
any computing platform, and is not dependent upon any specific
public-key algorithm.
Figure 1 illustrates an exemplary flowchart for a digital time
stamping method according to an embodiment of the present
invention. In step 1010 a key pair is generated at time
8
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
interval t;,. As is known in the art, the key pair includes a
public key and a private key. The time interval can be any
defined period, e.g., every second, 10 seconds, minute or 10
minutes. The current time interval is referred to as tn. In
step 1020, it is determined if a time stamp request is
received during time interval t,,. If no time stamp request is
received during time interval t,õ then the process returns to
step 1010 to generate a new key pair for the next time
interval, n being incremented by 1 to indicate the next time
interval.
If a time stamp request is received during time interval tn, in
step 1030 the data accompanying the time stamp request is
automatically signed. For example, a conventional message
digest for the data could be generated that would be
automatically encrypted using the private key of time interval
t,,. As a result of signing the data, the signature of the time
stamp can only be decrypted using the public key of time
interval t,. In step 1040, a time stamp certificate is
generated for delivery to the requestor indicating the
temporal existence of the data. In step 1050, it is
determined if additional time stamp requests are received
within time interval t;,.
If no additional time stamp requests are received, then the
private key for time interval tr, is deleted in step 1060 and
the process returns to step 1010 to generate a key pair for
the next time interval, n being incremented by 1. If further
time stamp requests are received during time interval tn, then
the process returns to step 1030 to process each further time
stamp request. As indicated in step 1060, the private key for
time interval tn is deleted at the end of the time interval and
the public key would be, for example, archived for subsequent
9
CA 02304342 2007-12-19
use to decrypt the time stamp. Thus, a separate private key
is used to automatically time stamp the data associated with a
time stamp request received during each defined time interval
according to an embodiment of the present invention.
The process according to an embodiment of the present
invention illustrated in Figure 1 differs from prior art
systems in that, for example, the key pairs are automatically
generated every defined time interval and the data
accompanying the time stamp request is automatically signed
using the private key of the time interval that the time stamp
request is received, the private key being deleted after the
time interval. In contrast, prior art time stamping systems
would use a single private key to sign all time stamp requests
and employ a separate mechanism, usually based on the computer
system implementing the time stamp, to provide the time stamp
data. Also unlike the time stamping method according to an
embodiment of the present invention, some prior art systems
would chain together the message digests for sequentially-
submitted documents that have been signed to generate the
message digest encrypted for the time stamp, for example, as
described in U.S. Patent No. 5,136,647.
Figure 2A illustrates an exemplary flowchart for a digital
time stamping method according to another embodiment of the
present invention. In step 2010 a key pair is generated. As
is known in the art, the key pair includes a public key and a
private key. According to an embodiment of the present
invention, a key pair is generated for each time interval
utilized by the system implementing the time stamping method.
The implementing system can include, for example, a
conventional general purpose computer, such as a
CA 02304342 2006-03-16
microprocessor based personal computer or server. In an
embodiment of the present invention, the method is implemented
in software that executes on a client-server computer system
architecture. The time interval can be any defined period,
e.g., every second, 10 seconds, minute or 10 minutes. The
current time interval is referred to as tn and the next time
interval is referred to as t,,l. For the purposes of time
stamping documents, accuracy to the minute may be sufficient
for subsequent authentication purposes.
In step 2020, another key pair is generated at time tn+l. Like
the first key pair, the next key pair also has a public key
and a private key. To generate the key pairs in steps 2010
and 2020, a conventional digital time stamping system such as
PGP could be modified to automatically generate key pairs
every defined time interval. For example, conventional
digital time stamping systems are designed for users to
generate key pairs, usually via user I/O with the system to
input the information necessary to generate a key pair (e.g.,
a pass phrase and a random seed required by PGP). According
to an embodiment of the present invention, the source code for
such systems could be modified to generate, for example, a
pass phrase and a random seed that would be automatically fed
to the key pair generation algorithm for each defined time
interval, thereby automatically providing the input normally
provided by a user to generate a key pair.
In step 2030, the public key of time interval tn+l is signed
using the private key of time interval t,,. For example, a
conventional message digest for the public key of time
interval tntl could be generated that would be encrypted using
the private key of time interval tn. As a result of signing
the public key of time interval t,, 1, the signature of the
public key can only be decrypted using the public key of time
11
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
interval tR. The signing of the public key of time interval
ti+1 using the private key of time interval tr, could be
accomplished, for example, using script based control of
existing software, such as the PGP software (e.g., a single
command line instructing that one key sign another key). In
step 2040, the private key of time interval tr, is deleted.
Thus, the private key for time interval t., exists for the
duration of time interval t~ and for the time necessary during
time interval tri+1 to sign the public key of time interval t,i1.
In step 2050, the public key for time interval tn is archived
for subsequent use, e.g., to decrypt the time stamp on the
public key of time interval tõi.
In step 2060, it is determined if a time stamp request is
received during time interval t,,l. If no time stamp request
is received, then the process returns to step 2020 to generate
a key pair for the next time interval, n being incremented by
1. If a time stamp request is received during time interval
t,.l, in step 2070, illustrated in Figure 2B, the data
accompanying the time stamp request is signed using the
private key of time interval t,,l. For example, as is known in
the art, a conventional message digest for the data to be time
stamped according to an embodiment of the present invention
could be generated that would be encrypted using the private
key of time interval trõ1. As a result of signing the data
using the private key of time interval t,,,,, the signature of
the time stamp could only be decrypted using the public key of
time interval tR,l, which public key itself has been time
stamped according to an embodiment of the present invention
and can be authenticated only using the public key of the
prior time interval t, as described above. Therefore, using an
embodiment of the method according to the present invention,
authentication of the time stamp on data is self-validated as
the keys for two time intervals have been chained together.
12
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
No independent third party is required to verify that the time
stamp on the data is accurate. In another exemplary
embodiment, the key pair for tn+l is generated and certified in
advance, during the end of the prior time interval t, to
insure that the key pair for time interval tn,l is available
immediately at the beginning of tR,l.
In step 2080, a stamp certificate is generated for delivery to
the requesting party. According to an exemplary embodiment of
the present invention, such a stamp certificate includes a
digital signature of the submitted data and the certified
public keys for time intervals t, and t.,,i. In step 2090, it is
determined if any additional time stamp requests are received
within time interval tr,,,. If no further time stamp requests
are received within time interval tn,l, the process returns to
point B on Figure 2A to generate the key pair for the next
time interval. If another time stamp request is received
during time interval tri1, in step 2100 the data accompanying
the time stamp request is signed using the private key of time
interval t.,,l as described above and the process loops back to
step 2090 until no further time stamp requests are received
during time interval tn,.l.
The method according to an embodiment of the present invention
for time stamping data can be implemented, for example as
software, firmware or hard-wired logic using a suitable
general purpose computer. For example, the software
implementation of the present invention can be written in the
Java programming language, that can run on any platform.
Figure 3A illustrates an exemplary client-server architecture
13
CA 02304342 2006-03-16
for implementing the time stamping method according to an
embodiment of the present invention. In a client-server
architecture, the server portion of time stamping program for
an embodiment of the present invention would reside in, for
example, a memory 3015 of the server 3010. The time stamping
program would execute on the cpu 3016 connected to the memory
3015. The server 3010 is connected to the client 3020 via,
for example, a connection 3030, such as a LAN, WAN or Internet
connection. The client computer 3020 would include a time
stamping client portion of the method according to an
embodiment of the present invention residing in a memory 3025,
the time stamping client program executing on the cpu 3026
connected to the memory 3025. An I/O device 3040, such as a
keyboard or mouse provides user access to the time stamping
method according to an embodiment of the present invention.
In operation, for example, a user would identify data to be
time stamped via the I/O device 3040 which would cause the
client application program stored in memory 3025,to execute in
cpu 3026 and generate a message digest for the data, for
example in a manner known in the art. The message digest
would be transmitted via connection 3030 to server 3010, where
the application program stored in memory 3015 would execute in
cpu 3026 to time stamp the message digest and return a time
stamp certificate to client computer 3020 via connection 3030,
for example as described in Figures 1 or 2A-2B.
In an alternative implementation of the client-server
architecture illustrated in Figure 3A, the signing could occur
at the client computer 3020. For example, via the I/O device
3040, a user could identify data to be time stamped and submit
the stamp request to the server computer 3010 via connection
3030 without providing a message digest for the data. In
14
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
response to the stamp request, the server 3010 would generate
a key pair for the current time interval according to an
embodiment of the present invention (e.g., with a public key
signed by the private key of the prior time interval key pair)
and return the key pair for the current time interval, the
passphrase for the time interval's private key, and the public
key from the prior time interval to the client computer 3020.
To ensure the secrecy of the transmission from the server 3010
to the client 3020, the connection 3030 can include, for
example, a secure channel using SECURE SOCKETS LAYER (SSL).
Once the client 3020 receives the transmission from the server
3010, the client can generate the message digest and sign the
message digest of the time stamp request using the private key
of the current time interval, for example in a manner as is
known in the art. After the time stamp is created, the
client-side copies of the associated private key and
passphrase are then immediately deleted.
In yet another alternative embodiment of the client-server
architecture illustrated in Figure 3A, the client computer
3020 can generate its own key pair and use a key pair
generated by the server 3010 to time stamp the public key of
the key pair generated by the client computer 3020. For
example, the client computer 3020 would generate a key pair
and transmit the public key of the key pair to the server 3010
via connection 3030. The private key of a key pair generated
by the server 3010 for the current time interval would be used
to sign the public key from the client 3020. The signed
public key and the public key of the key pair generated by the
server would be transmitted back to the client 3020. The
private key from the key pair generated by the client 3020
would be used to time stamp the data. Immediately after the
time stamp was produced, the client-side private key would be
immediately deleted, then the client-side public key would be
CA 02304342 2000-03-20
WO 99/16209 PCT/[3S98/20036
revoked by using the server-side private key to issue a
revocation certificate for the client-side public key. The
private key from the server 3010 would be destroyed. The
revocation certificate would be incorporated into the time
stamp certificate, together with the signature of the data,
the server-side public keys for the current and previous time
intervals, and the client-side public key.
Figure 3B illustrates an alternative embodiment for a system
implementing the time stamping method according to an
embodiment of the present invention. In Figure 3B, the time
stamping method is carried out in a single computer system
3100, such as a relational database system or a financial
transaction system. Computer system 3100 includes a memory
3115 connected to a cpu 3116. An I/O device 3140, such as a
keyboard or mouse, is connected to the computer 3100 and
provides user access to the time stamping method according to
an embodiment of the present invention. The memory 3115 would
contain, for example, both the resident program to generate
the message digests for data to be time stamped and the time
stamping program according to an embodiment of the present
invention.
According to the illustrative embodiment of Figure 3B, either
the user would identify data to be time stamped via the I/O
device 3140 or the system would automatically identify data to
be time stamped, for example as in response to a database
transaction. Identification of the data to be time stamped
then would cause the resident program stored in memory 3115 to
execute in CPU 3116 and generate a message digest for the
data. The message digest would be provided to the application
program, also stored in memory 3115, which would execute in
CPU 3116 to time stamp the data and return a time stamp
16
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
certificate to the resident program, which could cause the
time stamp certificate to be forwarded to the I/O device 3140
for the user.
Therefore, according to the present invention, key pairs are
generated for particular time intervals and time stamp
requests are automatically carried out using the private key
for the time interval, the private key being destroyed after
the time interval. In another embodiment of the present
invention, the private key of a prior time interval is used to
sign the public key for a subsequent time interval before the
private key of the prior time interval is destroyed. In this
embodiment of the present invention, every time interval has
its own key pair for which the private key is destroyed after
signing the public key for the next time interval. According
to the present invention, key pairs do not have to be
continuously generated every time interval, but can be pre-
generated and selected from a queue for each time interval
that a time stamp request is received.
The time stamping method according to an embodiment of the
present invention uses public key cryptography in a new way
to, first, create key pairs that correspond not to fixed
entities, such as previous systems employ, but which
correspond to transient time intervals; and second, to provide
a mechanism to use the keys, and signatures created by those
keys, to provide rigorous proof of the time of existence and
the authenticity of the content within data signed by the
system. As mentioned above, a feature of the system is that
the secret key for a given time interval only exists for a
finite, typically very short, period of time, and is replaced
by subsequent secret keys as subsequent time intervals
proceed. A public key cryptography system, such as PGP with
17
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
the above-described modifications, is employed to
automatically generate a series of public-key encryption key
pairs at regular time intervals. Each key contains a
designation, for example typically within the key's user ID,
which identifies the specific time interval during which it is
to be (or was) used. For dynamically-created keys, the
minimum possible duration of a time interval is limited by the
time necessary for creation of a key pair and the use of that
key pair to validate a public key. As indicated above,
shorter time intervals can be enabled by pre-generating the
key pairs.
As illustrated above, the veracity of the time designation is
proven by "chaining" of signatures, so that each new time
interval's public key is certified (e.g., digitally signed)
using the prior interval's secret key, immediately prior to
deleting that prior time interval's secret key. This is done,
for example, by using the prior time interval's secret key to
digitally sign the new time interval's public key.
Immediately after the public key is signed, the prior
interval's secret key is deleted
The public key of each key pair is stored for future use. Any
given private key is used for time-stamping data only during
the time interval immediately following the interval within
which the private key was generated. During its interval of
use, the secret key is used to digitally sign and time-stamp
all data submitted to the system for such processing. As data
is submitted to the system for time-stamping, these data are
processed by signing them using the respective time interval's
private key. This signing process generates a time-stamp
certificate. Each time-stamp certificate includes, for
example, the digital signature of the data generated by the
18
CA 02304342 2000-03-20
WO 99/16209 PCT/US98/20036
secret key and the certified public key for the current time
interval of use. Each interval-of-use's public key can be
also archived for future reference. For use in easy
authentication of time-stamp certificates in the future, all
time-stamp certificates can be archived as well, although such
time-stamp certificate archiving is not necessary for later
proof of the veracity of time-stamps generated by the system.
At the end of each time interval, a new key pair is generated,
the public key of the new pair is certified (e.g., signed) by
the current time interval's secret key, and that secret key is
then deleted, and the cycle continues. Validation of a time-
stamp at any later point requires using the respective time
interval's public key to authenticate the digital signature in
the time-stamp certificate. Validation of that public key is
accomplished by using the previous time interval's public key
to authenticate the certification signature on the public key
to be authenticated. The ability to trace back through the
"chain" of public key certification signatures provides
irrefutable proof of the location, in time, of any individual
time interval's stamp within the chain of signatures. Further
evidence of the exact time that a given time interval key was
in use can be provided by tracking other certificates that
were generated by the same key and collecting evidence of the
time of generation of those signatures and the signed data
relating to them. Since the secret key for each time interval
is destroyed immediately after that time interval passes, it
is virtually impossible to create a bogus time-stamp after the
fact.
Many other implementations of the time stamping method
according to an embodiment of the present invention are
possible as well. As described above, for example, one could
19
CA 02304342 2000-03-20
WO 99/16209 PCTIUS98/20036
calculate the message digests at the users' sites, and send
only those message digests to the server for signing. This
would both insure confidentiality of data and efficient
network bandwidth usage.
