US5136647A — Method for secure time-stamping of digital documents
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
|||||||||||||| US005.136647A
United States Patent (19) 11) Patent Number: 5,136,647
Haber et al. (45) Date of Patent: Aug. 4, 1992
(54) METHOD FOR SECURE TIME-STAMPING Attorney, Agent, or Firm-Leonard Charles. Suchyta;
OF DIGITAL DOCUMENTS Lionel N. White
(75) Inventors: Stuart A. Haber, New York, N.Y.; (57) ABSTRACT
Wakefield S. Stornetta, Jr., A system for time-stamping a digital document, includ
Morristown, N.J.
ing for example text, video, audio, or pictorial data,
(73) Assignee: Bell Communications Research, Inc., protects the secrecy of the document text and provides
Livingston, N.J. a tamper-proof time seal establishing an author's claim
(21) Appl. No.: 561,888 to the temporal existence of the document. Initially, the
author reduces the document to a number by means of
22 Filed: Aug. 2, 1990 a one-way hash function, thereby fixing a unique repre
5ll Int. Cl........................... H04L 9/00; H04L 9/30 sentation of the document text. In one embodiment of
52 U.S. C. ........................................ 380/49; 380/23; the invention the number is then transmitted to an out
380/25; 380/30 side agency where the current time is added to form a
(58) Field of Search .................... 364/200, 900; 380/3, receipt which is certified by the agency using a public
380/4, 30, 49,850, 5, 9, 10, 28 key signature procedure before being returned to the
(56) References Cited author as evidence of the document's existence. In later
proof of such existence, the certificate is authenticated
U.S. PATENT DOCUMENTS by means of the agency's public key to reveal the re
4,145,568 3/1979 Ehrat ................................ 380/50 X. ceipt which comprises the hash of the alleged document
4,405,829 9/1983 Rivest et al. ... 380/30 along with the time seal that only the agency could
4,972,474 11/1990 Sabin ................................. 380/49 X have signed into the certificate. The alleged document
OTHER PUBLICATIONS is then hashed with the same one-way function and the
original and newly-generated hash numbers are com
“New Directions in Cryptography", W. Diffie & M. E. pared. A match establishes the identify of the alleged
Hellman, IEEE Transactions. On Information Theory, document as the time-stamped original. In order to
vol. IT-22, Nov. 1976, pp. 644-654. prevent collusion in the assignment of a time stamp by
“Collision-Free Hash Functions & Public Key Signa the agency and thus fortify the credibility of the system,
ture Schemes', I. B. Damgdard, Adyanaces in Cryp the receipt is linked to other contemporary receipts
tology-Eurocrypt '87, Springer-Verlag, LNCS, 1988, before certification by the agency, thereby fixing a doc
vol. 304, pp. 203-216. ument's position in the continuum of time. In another
"Pseudorandom Generation From One-Way Func embodiment, a plurality of agencies are designated by
tions", R. Impagliazzo & L.A. Levin, Proc. 21st STOC, means of random selection based upon a unique seed
pp. 12-24, ACM, 1989. that is a function of the hash number of the document to
“The MD4 Message Digest Algorithm", R. L. Rivest be time-stamped. Thus being denied the ability to
Crypto '90 Abstracts, Aug. 1990, pp. 281-291. choose at will the identity of an agent, the author can
Alan G. Konheim, Cryptography, a Primer (John Wiley not feasibly arrange for falsification of a time stamp.
& Sons, Inc.; 1981); pp. 331-333.
Primary Examiner-Bernarr E. Gregory 18 Claims, 3 Drawing Sheets
U.S. Patent Aug. 4, 1992 Sheet 1 of 3 5,136,647
11
Author Prepares
Digital Document
f------------------- - 12
DOCunent r
Condensed
e.g., Hashed
Document ansmitted
O
Outside Agency
Agency Adds
Time Data
“g: Applies
ryptographic
Signature
Agency Transmits
Certificate
To Author
FIG. 1
U.S. Patent Aug. 4, 1992 Sheet 2 of 3 5,136,647
21
Author Prepares
Digital Document
DOCunent
Condensed
e.g., Hashed
DOCunent TranSnitted
To TSA
TSA AddS Tine
Data To
Create Receipt
TSAAdds
Data Fron
Adjacent Receipt(s)
TSA Applies
Cryptographic Signature
To Composite Receipt
TSA TranSnitS
Certificate
TO Author
FIG. 2
U.S. Patent Aug. 4, 1992 Sheet 3 of 3 5,136,647
Author Prepares
Digital Document
-
DOCunent
Condensed
e.g., Hashed
-
Seed
Pseudorandon
Generator
Select OutSide
Agency(s) According
To Generator Output
Document Transmitted
TO
Outside Agency(s)
Agency(s) Adds
Time Data
Agency(s) Return(s)
Certificate(s)Signature
Cryptographic With
FIG. 3
1.
5,136,647
2
No. 4,405,829, issued Sept. 20, 1983. While this scheme
METHOD FOR SECURE TIME-STAMPING OF expands the utilizing universe to a substantially unlim
DIGITAL DOCUMENTS ited number of system subscribers who are unknown to
BACKGROUND OF THE INVENTION
one another, but for a public directory, verifiable com
5 munications remain bilateral. These limitations persist,
In many situations there is a need to establish the date since although a public key "signature', such as that
on which a document was created and to prove that the which entails public key decryption of a message en
text of a document in question is in fact the same as that crypted with the private key of the transmitter, pro
of the original dated document. For example, in intel 10 vides any member of the unlimited universe with signifi
lectual property matters it is often crucial to verify the cant evidence of the identity of the transmitter of the
date on which a person first put into writing the sub message, only a given message recipient can be satisfied
stance of an invention. A common procedure for thus that the message existed at least as early as the time of its
"time-stamping' an inventive concept comprises daily receipt. Such receipt does not, however, provide the
notations of one's work in a laboratory notebook. Indel 15 whole universe with direct evidence of time of the
ibly dated and signed entries are made one after another message's existence. Testimony of such a recipient in
on each page of the notebook where the sequentially conjunction with the received message could advance
numbered, sewing pages make it difficult to revise the the proof of message content and time of its existence,
record without leaving telltale signs. The validity of the but such evidence falls victim to the basic problem of
record is further enhanced by the regular review and ready manipulation of electronic digital document con
signed witnessing by a generally disinterested third 20 tent, whether by originator or witness.
party. Should the time of the concept become a matter Thus, the prospect of a world in which all documents
for later proof, both the physical substance of the note are in easily
book and the established recording procedure serve as substance ofmodifiable digital form threatens the very
effective evidence in substantiating the fact that the credibility of such documents. Thereforis establishing
existing procedures
clearly a
the
signifi
concept existed at least as early as the notebook witness cant present need for a system of verification by which
25
date.
The increasingly widespread use of electronic docu athat digital document may be so fixed in time and content
ments, which include not only digital representations of nizedit incantangible
present, at least to the extent currently recog
documents, direct evidence on those
readable text but also of video, audio, and pictorial data, issues.
now poses a serious threat to the viability of the "note 30
book" concept of establishing the date of any such doc SUMMARY OF THE INVENTION
ument. Because electronic digital documents are so The present invention yields such a reliable system in
easily revised, and since such revisions may be made
without telltale sign, there is available limited credible a method of time-stamping digital documents that pro
evidence that a given document truly states the date on 35 vides the equivalent of two essential characteristics of
which it was created or the message it originally car accepted document verification. First, the content of a
ried. For the same reasons there even arises serious document and a time stamp of its existence are "indeli
doubt as to the authenticity of a verifying signature. bly' incorporated into the digital data of the document
Without an effective procedure for ensuring against the so that it is not possible to change any bit of the result
surreptitious revision of digital documents, a basic lack ing time-stamped data without such a change being
of system credibility prevents the efficiencies of elec apparent. In this manner, the state of the document text
tronic documentation from being more widely imple is fixed at the instant of time-stamping. Second, the time
mented. at which the digital document is stamped is verified by
Some procedures are presently available for verifying a "witnessing' digital signature procedure that deters
electronic document transmissions; however, such pro 45 the incorporation of a false time statement. In essence,
cedures are limited in application to bilateral communi the method transfers control of the time-stamping step
cations. That is, in such communications the sender from the author to an independent agent and removes
essentially desires to verify to the receiver the source from the author the ability to influence the agent in the
and original content of the transmitted document. For application of other than a truthful time stamp.
example, "private key” cryptographic schemes have 50 The method of the present invention presumes a num
long been employed for message transmission between ber of document authors distributed throughout a com
or among a limited universe of individuals who are munication network. Such authors may be individuals,
known to one another and who alone know the de companies, company departments, etc. each represent
crypting key. Encryption of the message ensures against ing a distinct and identifiable, e.g. by ID number or the
tampering, and the fact that application of the private 55 like, member of the author universe. In one embodiment
key reveals the "plaintext" of the transmitted message of the invention, this universe may constitute the clien
serves as proof that the message was transmitted by one tele of a time-stamping agency (TSA), while in another
of the defined universe. The time of creation of the embodiment the distributed authors may serve as agents
message is only collaterally established, however, as individually performing the time-stamping service for
being not later than its receipt by the addressee. This other members of the universe.
practice thus fails to provide time-stamp evidence that In its general application as depicted in FIG. 1 of the
would be useful in an unlimited universe at a later date. drawing, the present method entails an author's prepa
A more broadly applicable verifying communication ration of a digital document, which may broadly com
procedure, that of "public key" cryptography, has been prise any alphanumeric, audio, or pictorial presentation,
described by Diffie and Hellman ("New Directions in 65 and the transmission of the document, preferably in a
Cryptography", IEEE Transactions On Information condensed representative form, to the TSA. The TSA
Theory, Vol. IT-22, November 1976, pp. 644-654) and time-stamps the document by adding digital data signi
more recently implemented by Rivest et al. in U.S. Pat. fying the current time, applying the agency's crypto
3. 5,136,647
4.
graphic signature scheme to the document, and trans however, relies upon a following additional aspect of
mitting the resulting document, now a certificate of the the invention.
temporal existence of the original document, back to the One embodiment of this segment of the process, as
author where it is held for later use in required proof of generally depicted in FIG. 2, draws upon the relatively
such existence. 5 continuous flow of documents from the universe of
To ensure against interception of confidential docu authors through the facilities of the TSA. For each
ment information during transmission, and to reduce the given processed document Dk, the TSA generates a
digital bandwidth required for transmission of the entire time-stamp receipt which includes, for example, a se
document, the author may optionally convert the digi quential receipt number, r, the identity of the author,
tal document string to a unique number having vastly O Ak, by ID number IDk, or the like, the hash, Hk, of the
reduced digital size by means of a deterministic function document, and the current time, tk. In addition, the
which may, for example, be any one of a number of TSA includes the receipt data of the immediately pre
algorithms known in the art as "oneway hash func ceding processed document, Dk-1, of author, Ak-1,
tions'. Such an application of hash functions has been thereby bounding the timestamp of document, Dk, in
described, among others, by Damgard in his discussions 15 the "past" direction by the independently established
on the improvement of security in document signing earlier receipt time, t-1. Likewise, the receipt data of
techniques ("Collision-Free Hash Functions and Public the next received document, Dk 1, are included to
Key Signature Schemes", Advances in Cryptology bound the time-stamp of document, Dk, in the "future'
Eurocrypt '87, Springer-Verlag, LNCS, 1988, Vol. 304, direction. The composite receipt, now containing the
pp. 203-217). In practice of the present invention, how time data of the three, or more if desired, sequential
ever, the "one-way' characteristic typical of a hashing time-stamp receipts, or identifying segments thereof, is
algorithm serves an additional purpose; that is, to pro then certified with the cryptographic TSA signature
vide assurance that the document cannot be revised and transmitted to the author, Ak. In like manner, a
subsequent to the time the TSA applies its time stamp. certificate containing identifiable representations of Dk
A hashing function provides just such assurance, 25 and Dk-2 would be transmitted to author, Ak. 1. Thus,
since at the time a document is hashed there is created
a representative "fingerprint" of its original content each fixed
of the time-stamp certificates issued by the TSA is
in the continuum of time and none can be falsely
from which it is virtually impossible to recover that prepared by the TSA, since a comparison of a number
document. Therefore, the time-stamped document is of relevant distributed certificates would reveal the
not susceptible to revision by any adversary of the au 30 discrepancy in their sequence. So effective is such a
thor. Nor is the author able to apply an issued time sequential fixing of a document in the time stream that
stamp certificate to a revised form of the document,
since any change in the original content, even to the the tice.
TSA signature could be superfluous in actual prac
-
extent of a single word or a single bit of digital data,
results in a different document that would hash to a 35 ally in FIG. 3, distributes the invention,
A second embodiment of the shown gener
time-stamping task ran
completely different fingerprint number. Although the domly among a broad universe, for example the multi
original document can thus not be recovered from the plicity of authors utilizing the time-stamping process. A
hashed document, a purported original document can TSA could still be employed for administrative pur
nonetheless be proven by the fact that a true copy of the
original document will always hash, assuming use of the poses or the requesting author could communicate di
same hashing algorithm, to the original number con rectly In either
with the selected time-stamping author/agents.
event, the above-mentioned need for assurance
tained in the certificate. that a time-stamp has not been applied to a document
Any available deterministic function, e.g. a one-way through collusion between the author and the stamping
hash function such as that described by Rivest ("The
MD4 Message Digest Algorithm", Advances in Cryp 45 agency premise
is met in the combination of the reasonable
that at least some portion of the agency uni
tology-Crypto, '90, Springer-Verlag, LNCS, to ap verse is incorruptible or would otherwise pose a threat
pear), may be used in the present procedure. In the of exposure to an author attempting falsification, and
practice of the invention, such a hashing operation the fact that the time-stamping agencies for a given
would normally be employed by the author to obtain document are selected from the universe entirely at
the noted benefit of transmission security, although it 50 random. The resulting lack of a capability on the part of
might be effected by the TSA if the document were the author to select a prospective collusive agent of the
received in plaintext form. In whatever such manner the author's own choosing substantially removes the feasi
document content and incorporated time data are fixed bility of intentional time falsification.
against revision, there remains the further step, in order The selection of the individual universe members
to promote the credibility of the system, of certifying to 55 who will act as the predetermined number of agents is
the members of an as yet unidentified universe that the accomplished by means of a pseudorandom generator
receipt was in fact prepared by the TSA, rather than by of the type discussed by Impagliazzo, Levin, and Luby
the author, and that the time indication is correct, i.e. ("Pseudorandom Generation From One-Way Func
that it has not, for instance, been fraudulently stated by tions", Proc. 21st STOC, pp. 12-24, ACM, 1989) for
the TSA in collusion with the author. which the initial seed is a deterministic function, such as
To satisfy the former concern, the TSA uses a verifi a hash, of the document being time-stamped. Given as a
able signature scheme, of a type such as the public key seed input the document hash or other such function,
method earlier noted, to certify the time-stamp prior to the implemented pseudorandom generator will output a
its transmittal to the author. Confirmation of the signa series of agency IDs. This agency selection is for all
ture at a later time, such as by decryption with the 65 practical purposes unpredictable and random.
TSA's public key, proves to the author and to the uni Once the agents are selected, the time-stamping pro
verse at large that the certificate originated with the ceeds as previously indicated with the exception that
TSA. Proof of the veracity of the time-stamp itself, each agent individually adds the current time data to the
5
5,136,647
6
representative document it receives, certifies the result By means of the md4 algorithm, the document is
ing separate time-stamped receipt with its own verifi hashed, at optional, dashed step 22, to a number, Hk, of
able cryptographic signature, and transmits the certifi a standard 128 bit format which expressed in base 16
cate back to the author. This transmittal may be directly appears as:
to the requesting author or by way of the administrative
TSA where the receipts are combined with or without
further certification by the TSA. The combination of
signature scheme and a published directory of author The author, Ak, whose system identification number
IDs provides verification of the utilization of the agents IDk, is i72 in a 1000 member author universe, transmits
that were in fact selected by the pseudorandom genera 10 the thus-identified document to the system TSA, at step
tor. This distributed agent embodiment of the invention 22, as the message, (IDkH), which appears:
presents some advantages over the receiptlinking proce
dure in that a certified time-stamp is provided more
quickly and a given author's later proof of a document
is less reliant upon the availability of the certificates of 15 as a request that the document be time-stamped.
other authors. The TSA then prepares the receipt for document, Dk,
Additional variations in the process of the invention by adding, at step 25, a sequential receipt number, r, of
might include the accumulation of documents, prefera 132, for example, and a statement of the current time, t.
bly in hashed or other representative form, generated This time statement might include a standard 32 bit
within an author organization over a period of time, e.g. 20 representation of computer clock time plus a literal
a day or more depending upon the extent of activity, statement, i.e. 16:37:41 Greenwich Mean Time on Mar.
with the collection being hashed to present a single 10, 1990, in order to allow the final time-stamp certifi
convenient document for time-stamping and certifica cate to be easily readable by the author, Ak. The receipt
tion. Also, the initial seed for the pseudorandom genera would then comprise the string, (rktkIDkHk).
tor may be based upon a function of time or previously 25 At this point it would be appropriate to further con
receipted documents, as well as of the document. The sider the earlier-mentioned reduction of number size to
implementation of the process may be automated in representative segments. As is described by Rivest et al.
simple computer programs which would directly carry in U.S. Pat. No. 4,405,829, the cryptographic public key
out the described steps of hashing and transmitting scheme to be employed in this example (generally
original documents, selecting time-stamping agents, 30 known in the field as the "RSA" signature scheme)
applying current time stamps, and returning certified requires the division of an extended message into blocks
receipts. that may each be represented by a number not exceed
THE DRAWING ing the encoding key number element, n. Each such
block is then signed with the RSA algorithm, to be
The present invention will be described with refer 35 reassembled after transmission. Therefore, in order to
ence to the accompanying drawing of which: be able to use a number, n, of reasonable size in this
FIG. 1 is a flow diagram of the general process of example while maintaining a single block for the final
time-stamping a document according to the invention; receipt string to be certified with the RSA scheme, each
FIG. 2 is a flow diagram of a specific embodiment of element of the receipt string will be reduced to a repre
the process; and 40 sentative eight bits, typically the last eight bits of any
FIG. 3 is a flow diagram of another specific embodi overlong string, and those bits will be stated in base 16
ment of the process. to present a two hexadecimal character string. Thus, for
DESCRIPTION OF THE INVENTION instance, the 128 bit document hash, Hk, will be repre
sented by its last eight bits, i.e. 0001 0101, stated as 15
The following examples of the application of embodi 45 (base 16). Likewise, IDk, 172, is 1010 1100 and is repre
ments of the present invention will serve to further sented by ac (base 16). Without actually undertaking the
describe the involved process. For convenience in the calculation, it will suffice to assume that the time state
presentation of these examples, the deterministic func ment, t, is represented as 51. The receipt number, 132,
tion selected is the md4 hashing algorithm described by would be represented as 84. The receipt string to this
Rivest, as mentioned above, and the verifiable signature 50 point, i.e. (r,tkIDk,H) now appears as 8451ac15.
scheme is the public key method suggested by Diffie Assume now that the immediately preceding docu
and Hellman, as implemented by Rivest et al. in U.S. ment, Dk-1, was processed by the TSA as the request:
Pat. No. 4,405,829. Further, in order to simplify expla
nation of the process and for the additional reasons
noted below, only representative segments of the entire 55
numbers will be employed. at 16:32:30 on Mar. 10, 1990 (tk- being represented as
The receipt-linking embodiment of the invention 64). The TSA adds these data at step 27, to the receipt
shown in FIG. 2 is initially considered. Although the string for Dk to yield the hexadecimal representation,
present process may be used with documents of any 845lac1564c974. This receipt Rk, now contains data
length, the following apt excerpt is amply representa fixing the time for Dk and a time, tR-1, before which
tive of a document, Dk, which an author prepares at author, Ak, cannot claim that Dk existed. This limitation
step 21 and for which time-stamping is desired: on Akis established by the fact that the previous author,
Time's glory is to calm contending kings, To unmask Ak-, holds a time certificate, Ck-1, that fixes t-1 as
falsehood, and bring truth to light, To stamp the seal Subsequent to the linked time data, t-2, in the certifi
of time in aged things, To wake the morn, and senti 65 cate of author, Ak-2, and so on for as long as a proof
nel the night, To wrong the wronger till he render requires.
right; To establish that TSA in fact originated the receipt
The Rape of Lucrece for document, Dk that receipt is transmitted, at step 29,
7
5,136,647
8
to author, Ak, after TSA signing, at step 28, with the The resulting seed hash:
public key cryptographic signature scheme and be
comes the certified receipt, or certificate, Ck. With the
data derived above, and assuming that TSA has the
RSA signature key set, in decimal: 5 represents the 128 bit number which mod 1000 is 487,
the ID of the first selected witness. The next witness is
<n, es = <43200677821428109, 1912 (Public) likewise chosen using this seed hash representation as
the seed in the second selection computation to yield:
<n, d = <43200677821428 109, 29403602422449791 > (Private)
O
the signed certificate for Rk, 8451ac1564c974, would
compute as: which mod 1000, is 571, the second witness ID. A re
peat of the computation, again seeding with the prior
Rimod n=39894704664774392 seed hash, selects the final witness as 598, which is:
15
When author, Ak, receives this certificate, Ck, along 2fe8768ef3532f15c40acf.34902cle nod 000
with the literal statement of Rk, it may be readily con
firmed as being correct by application of the TSA pub The TSA now sends, at step 37, a copy of the original
lic key to verify that: request to each of these three witnesses who individu
20 ally, at step 38, add a current time statement and ID,
Cimod n=Rik and certify the resulting receipts by signing with the
RSA cryptographic signature scheme and transmitting
and that Rk in fact contains the data representing the them, at step 39, directly to the author or through the
document hash, Hk. TSA who may assemble the certificates into a file to be
The procedure shown in this simple one-link example 25 delivered to the author. By virtue of the fact that the
results in a certificate which, being bounded in time by pseudorandom generation prevents the exercise of a
the data from document, Dk, provides author, Ak-1 personal choice in the selection of witnesses, the author
with reliable evidence that document, Dk-1, was not is deterred by the risk of encountering a non-coopera
backdated to a time significantly prior to the existence tive witness from attempting any communication prior
of document, Dk. When the certificate of Ak is ex 30 to time stamp certification for the purpose of arranging
panded with additional data from the subsequently pro for a false time entry. In a process variant where the
cessed document, Dk-1, it will likewise be effectively author is allowed to transmit the request directly to
bounded to substantiate the time stamp claimed by Ak. witnesses, the random selection of such witnesses which
In an alternative of the same effect, Ak could simply be is keyed essentially to the involved document itself
advised of the identity of Akl and could confirm from 35 frustrates any attempt by the author to direct the docu
that author that the one-link certificate, Ck, con ment to a known cooperative witness. The group of
tained the element, Hk. The procedure could also be resulting certificates may thus be employed with confi
varied to provide certified receipts which include data dence in later proofs employing signature verification in
from any number of authors, with each addition provid the manner earlier described.
ing a further degree of assurance against falsification. 40 The procedures described and variants suggested
Another embodiment of the invention, as shown in herein for the practice of this time-stamping process and
FIG. 3, which utilizes randomly selected members of the various other embodiments which will become ap
the author universe as time-stamping agents, or wit parent to the skilled artisan in the light of the foregoing
nesses, i.e. a "distributed trust' procedure, would pro description are all nonetheless to be included within the
ceed in the following manner. Although these numbers 45 scope of the present invention as defined by the ap
are not so limited in actual practice, for purposes of the pended claims.
example it will be assumed that the universe consists of What is claimed is:
1000 authors, having IDs 0-999, and that three wit. 1. A method of time-stamping a digital document
nesses will be sufficient to establish the veracity of the which comprises:
time stamp. Also, in this example the earlier-noted vari 50 a) transmitting a digital representation of said docu
ation including the services of a TSA is being imple ment from an originator to an outside agency;
mented. The hashing function, md4, utilized in the b) creating at said outside agency a receipt compris
above example is employed here also, in optional step ing a digital representation of then current time and
32, as an example of a deterministic document function at least a portion of a digital representation of said
which will seed the pseudorandom selection of the 55 digital document; and
three witnesses from the author universe. c) certifying said receipt at said outside agency by
As in the previous example, the author transmits the means of a verifiable digital cryptographic signa
document to the TSA, normally in hashed form, as the ture scheme.
identified request: 2. A method of time-stamping a digital document
according to claim 1 wherein said transmitted digital
document representation comprises at least a portion of
the digital representation of the number derived by
The TSA now uses this document hash string, in step application of a deterministic function algorithm to said
33, as the seed to generate the ID number of the first digital document.
witness, at step 35, according to the selection algorithm: 65 3. A method of time-stamping a digital document
according to claim 1 wherein said receipted digital
ID=(md4(seed)mod(universe size) document representation comprises at least a portion of
the digital representation of the number derived by
5,136,647
10
application of a deterministic function algorithm to said additional outside agency selected by said pseudoran
digital document. dom generation.
4. A method of time-stamping a digital document 13. A method for the secure time-stamping of a digital
according to claim 3 wherein said digital number repre document
sentation is derived from the application of a one-way 5 characterized in that
hashing algorithm to said digital document. a) a digital representation of said document is trans
5. A method of time-stamping a digital document mitted from an originator to an outside agency;
according to claim 1 wherein said receipt further com b) said outside agency creates a receipt comprising a
prises the time representation and digital document digital representation of then current time and at
representation specific to at least one other digital docu 10 least a portion of a digital representation of said
ment receipted by said outside agency, digital document; and
6. A method of time-stamping a digital document c) said receipt is certified at said outside agency by
according to claim 5 wherein the receipt of said at least means of a verifiable digital cryptographic signa
one other digital document was created by said outside ture scheme.
agency earlier than that of the currently receipted digi 15 14. A method for the secure time-stamping of a digital
tal document. document according to claim 13
7. A method of time-stamping a digital document characterized in that said receipt further comprises
according to claim 5 wherein the receipt of said at least the time representation and digital document repre
one other digital document was created by said outside sentation specific to at least one other digital docu
agency later than that of the currently receipted digital 20 ment receipted by said outside agency.
document. 15. A method for the secure time-stamping of a digital
8. A method of time-stamping a digital document document according to claim 14
according to claim 1 wherein said outside agency is characterized in that the receipt of said at least one
selected at randon from a predetermined universe. other digital document was created by said outside
9. A method of time-stamping a digital document 25 agency later than that of the currently receipted
according to claim 8 wherein said outside agency is digital document.
selected by means of a pseudorandom generator seeded 16. A method for the secure time-stamping of a digital
with at least a portion of the digital representation of the document according to claim 13
number derived by application of a deterministic func characterized in that said outside agency is selected at
tion algorithm to said digital document. 30 random from a predetermined universe by means
10. A method of time-stamping a digital document of a pseudorandom generator seeded with at least a
according to claim 9 wherein said pseudorandom gener portion of the digital representation of the number
ation seed is derived from the application of a one-way derived from the application of a deterministic
hashing algorithm to said digital document. function algorithm to said digital document.
11. A method of time-stamping a digital document 35 17. A method for the secure time-stamping of a digital
according to claim 10 which further comprises the like document according to claim 16
preparation of a time-stamp certificate by at least one characterized in that said seed is derived from the
additional outside agency selected by said pseudoran application of a one-way hashing algorithm to said
dom generation and wherein the input for each addi digital document.
tional outside agency selection is at least a portion of the 18. A method for the secure time-stamping of a digital
digital representation of the output derived from the document according to claim 16
application of said one-way hashing algorithm to a digi characterized in that a time-stamp certificate for said
tal representation of the previously generated output. digital document is likewise prepared by at least
12. A method of time-stamping a digital document one additional outside agency selected by means of
according to claim 9 which further comprises the like 45 said pseudorandon generation.
preparation of a time-stamp certificate by at least one k s
50
55
60
65