Digital document authentication system

• US 5,781,629 A
• Filed: 02/21/1997
• Issued: 07/14/1998
• Est. Priority Date: 10/28/1994
• Status: Expired due to Term

• Current Assignee: Surety, LLC
• Original Assignee: Surety Technologies Incorporated
• Inventors: Haber, Stuart A., Stornetta, W. Scott Jr.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/803,326
• Time in Patent Office: 508 Days
• Field of Search: 380/23, 380/28, 380/30
• US Class Current: 713/177
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

A process for time-stamping a digital document is provided. The process provides a certificate which not only allows for the authentication of a document at a later time but which includes a name or nickname which allows for the unique identification of the document at a later time. The name or nickname provided in accordance with the present invention is not only simple and concise but allows for the self-authentication of the document which it refers to. The name can be used when two independent parties desire to refer to the same unique document in a quick and simple way.

Claims

1. A method for processing a plurality of digital documents comprising the step of electronically generating a repository of hashed digital values in the form of a directed acyclic graph having nodes, each node comprising a hash value dependent on at least one of said digital documents, and the repository having a secured value comprising a hash value derived from more than one of said digital documents and generating a location pointer in the repository for one of the plurality of digital documents and naming said one digital document to provide a self-verifying name for said one digital document.

2. A certificate for a digital document, the certificate generated by processing a plurality of digital documents by electronically generating a repository of digital hash values in the form of a directed acyclic graph having nodes, wherein each of said nodes in the repository is determined by a hash value of at least one of said digital documents and generating a location pointer in the repository for one of the plurality of digital documents and naming said one digital document to provide a self-verifying name for said one digital document.

3. The certificate of claim 2, wherein the certificate authenticates the digital document.

4. The certificate of claim 2, wherein the certificate time-stamps the digital document.

5. A method for validating a first digital document purported to be a true copy of a previously registered second digital document, wherein the second digital document was registered by generating a certificate including a self-verifying name, self-verifying hash values for the second document, and associated location values for said self-verifying hash values wherein the self-verifying name comprises a combination of said location values and an identifier of a secure hash value, the method comprising the steps of:

(a) providing the secure hash value determined at least in part by the hash value of the second document;

(b) hashing the first digital document to provide a first digital document hash value;

(c) hashing and combining the first digital document hash value with said self-verifying hash values according to said location values; and

(d) determining whether a resulting hash value from step (c) corresponds to the secure hash value.

6. The method of claim 5 wherein the step of combining comprises concatenating.

7. The method of claim 5 wherein the step of providing the secure hash value comprises either (1) publishing an item directly or (2) linking an item to another item that is published directly.

8. The method of claim 7 wherein said published hash value is published some time after the second document is registered.

9. The method of claim 5 further comprising the step of linking the secure hash value to another hash value that is directly published.

10. A method of registering a first digital document for authentication, comprising the steps of:

a. transmitting from an author to a service bureau, a first request for registering the first digital document, the first request including a representation of the first digital document;

b. receiving at the service bureau the first request for registering the first digital document;

c. receiving at the service bureau a plurality of other requests for registering other digital documents, each request including a representation of one of the plurality of other digital documents;

d. the service bureau combining the first request with at least one of the plurality of other requests to form a first value;

e. the service bureau hashing the first value to generate a first hash value;

f. the service bureau forming a repository of a plurality of hash values including said first hash value, the repository depending on the first request and the plurality of other requests;

g. securing the repository by publishing an item in the depository, the item determined at least in part by a request;

h. the service bureau generating a location pointer in the repository for the first digital document, and

i. the service bureau providing a self-verifying name to the digital document by using the location pointer.

11. The method of claim 10 wherein the step of combining comprises concatenating.

12. The method of claim 10 wherein said repository is a tree and the step of publishing the item comprises publishing a root of said tree.

13. The method of claim 10 wherein said published item has an identifier comprising a user-friendly representation of the date or time at which the item was computed.

14. The method of claim 10 wherein a local entity also performs steps (b) and (c) to form a local repository having a local item to be secured and wherein the local entity subsequently sends a first request comprising said local item to the service bureau which performs step (b) through (i).

15. The method of claim 14 wherein steps (c), (d), and (e) are performed by said service bureau and further includes the step of combining said local item with another hash value.

16. The method of claim 14 further comprising the step of including in the local repository a hash value of a table of contents for a plurality of related documents.

17. The method of claim 14 further comprising the step of including in the local repository a plurality of items corresponding to a plurality of portions of a multi-part document.

18. The method of claim 10 wherein the repository is a binary tree.

19. The method of claim 10 wherein the repository is a linked list.

20. The method of claim 10 wherein the repository is a growing directed acyclic graph.

21. The method of claim 10 wherein the step of combining further comprises the step of combining roots of frequently computed trees to form less-frequently computed trees whose roots are in turn combined into linear linked lists.

22. The method of claim 10 wherein the step of generating the location pointer further comprises determining a list of self-verifying hash values for the first document and associated location values for said self-verifying hash values.

23. The method of claim 22, wherein the step of providing a self-verifying name further comprises naming said first document by an identifier of said published item and by said location values to provide the self-verifying name for said first document.

24. The method of claim 22 wherein said step of providing a self-verifying name for said first document further comprises applying a compact encoding algorithm to a combination of said associated location values and an identifier of said published item to provide a simplified alpha-numeric name for said first document.

25. The method of claim 10 wherein the step of providing a self-verifying name further includes the step of a requester choosing a first portion of said self-verifying name for certifying the first document.

26. The method of claim 25 wherein the step of choosing the first portion of the self verifying name further comprises choosing information associated with the first document.

27. The method of claim 25 wherein the first portion of the self-verifying name provides information about the requester for certifying the first document.

28. The method of claim 10, further comprising the step of the service bureau generating a certificate for said first digital document including the self verifying name.

29. The method of claim 28, further comprising the service bureau transmitting the certificate to the author.

30. The method of claim 28 wherein the step of generating the certificate further comprises the step of including on the certificate the list of self-verifying hash values.

31. The method of claim 28 wherein the step of generating the certificate occurs substantially prior to a time at which an item of the repository is published.

32. The method of claim 28 further comprising the step of transmitting the certificate to a storage facility and transmitting the self-verifying name to the originator of the first request.

33. The method of claim 10, wherein the step of receiving requests further comprises receiving requests from a plurality of users.

34. A certificate authenticating a digital representation of a document, said certificate generated according to the method of claim 10.

35. A method for naming a first digital document, comprising the steps of:

a. transmitting from an author to a service bureau a first request for naming the first digital document, the first request including a representation of the first digital document;

b. the service bureau receiving the first request;

c. receiving at the service bureau a plurality of other requests for naming digital documents, each request including a representation of one of the plurality of other digital documents;

d. the service bureau combining the first request with at least one of the plurality of requests to form a first value;

e. the service bureau hashing the first value to generate a first hash value;

f. the service bureau forming a repository of a plurality of hash values including said first hash value, the repository being in the form of a directed acyclic graph having nodes, each node comprising a hash value dependent on at least one of said requests, and said repository also having a secured item comprising a hash value dependent on a plurality of said requests;

g. the service bureau generating a location pointer in the repository for the first digital document; and

h. the service bureau naming said first digital document using said location pointer to provide a self-verifying name for said first digital document.

36. The method of claim 35 wherein the step of combining comprises concatenating.

37. The method of claim 35 further including the step of securing the repository by publishing an item of the repository, the item determined at least in part by at least one request.

38. The method of claim 37 wherein the step of generating the location pointer further comprises determining a list of self-verifying hash values for the first document and associated location values for said self-verifying hash values.

39. The method of claim 38 wherein the step of naming further comprises naming said first document by an identifier of said published item and by said location values to provide the name of said first document.

40. The method of claim 39 wherein said step of naming said first document further comprises applying a compact encoding algorithm to a combination of said associated location values and said identifier of said published item to provide a simplified alpha-numeric name for said first document.

41. The method of claim 37 wherein the published item has an identifier comprising a user-friendly representation of the date or time at which the item was computed.

42. The method of claim 35 wherein said repository is a tree and said secured item is a root of said tree.

43. The method of claim 35 wherein a local entity also performs steps (b) through (f) to form a local repository having a local item to be secured and wherein the local entity subsequently sends a second request comprising said local item to the service bureau which performs steps (b) through (h).

44. The method of claim 43 wherein steps (c) through (f) are performed by said service bureau and the service bureau further performs combining said local item with another hash value.

45. The method of claim 43 further comprising the step of including in the local repository a hash value of a table of contents for a plurality of related documents.

46. The method of claim 43 further comprising the step of including in the local repository a plurality of items corresponding to a plurality of related documents with location information encoded so as to provide first portions of said names that correspond substantially exactly to the logical structure of the relationships among the documents named.

47. The method of claim 35 wherein the step of naming further includes the step of a requester choosing a first portion of said name for naming the first document.

48. The method of claim 47 wherein the step of choosing further includes choosing the first portion of the name to provide information associated with the first document.

49. The method of claim 47 wherein the first portion of the name provides information about the requester for naming the first document.

50. The method of claim 35 wherein the repository is a binary tree.

51. The method of claim 35 wherein the repository is a linked list.

52. The method of claim 35 wherein the step of combining further comprises the step of combining roots of frequently computed trees to form less-frequently computed trees whose roots are in turn combined into linear linked lists.

53. The method of claim 35 further including the step of transmitting the name to a requester and wherein step (h) occurs substantially prior to a time at which an item of the repository is caused to be published.

54. The method of claim 35, further including the step of the service bureau generating a certificate for said first digital document including the self-verifying name.

55. The method of claim 54 further including the step of transmitting the certificate to the author.

56. The method of claim 35, wherein the step of receiving requests further comprises receiving requests from a plurality of users.

57. A certificate authenticating a digital representation of a document, said certificate including a name generated according to the method of claim 35.

58. A method for time stamping a first digital document, comprising the steps of:

a. preparing a first request to time stamp the first digital document, the request including a hash value of the first digital document;

b. combining the first request with a second hash value to generate a composite digital value, the second hash value being dependent at least in part on a second digital document;

c. hashing the composite digital value to generate a first composite hash value; and

d. forming a repository of hashed digital values including the first composite hash value, the repository being a directed acyclic graph having nodes, each node comprising a hash value which is dependent on at least one received request, and the repository also having a secured item comprising a hash value dependent at least in part on at least one of the received requests; and

e. providing a unique, self-verifying name for the first digital document by;

i. securing an item in the repository;

ii. generating an identifier for the secured item; and

iii. providing the unique, self-verifying name for the first digital document using the identifier and location values related to a location of the first digital document with respect to the secured item.

59. The method of claim 58, wherein before the step of combining the first request with the second hash value, receiving the second digital document as part of a second request to time stamp.

60. The method of claim 58, wherein the step of combining further comprises concatenating the first request and the second hash value.

61. The method of claim 58, wherein the step of forming a repository further comprises the steps of:

a. receiving a plurality of requests, each request including a representation of a digital document and forming a node of the repository;

b. combining at least two requests together to form a second composite digital value;

c. hashing the second composite digital value; and

d. continuing combining and hashing composite digital values until a secured item in the repository is formed.

62. The method of claim 61, wherein the step of receiving further comprises receiving requests from a plurality of users.

63. The method of claim 58, wherein the second digital document is a pre-existing hash value and the step of forming a repository further comprises the steps of:

a. combining the first composite hash value with a second request, to generate a second composite digital value;

b. hashing the second composite digital value to generate a second composite hash value;

c. combining the second composite hash value with a third request, to generate a third composite digital value;

d. hashing the third composite digital value to generate a third composite hash value; and

e. continuing combining requests with composite hash values to generate resultant composite digital values and hashing the resultant composite digital values.

64. The method of claim 58, further comprising after the step of forming a repository:

a. determining an item in the repository to be the secured item; and

b. securing the item.

65. The method of claim 64, wherein the step of securing further comprises publishing an item that includes a hash value based at least in part on a request.

66. The method of claim 65, wherein the step of securing further comprises publishing a second item to which the selected item is linked.

67. The method of claim 58, further comprising after the step of forming a repository, generating a certificate.

68. The method of claim 67, wherein the step of generating the certificate further comprises the step of calculating hash values which authenticate the first digital document.

69. The method of claim 68, wherein the step of generating the certificate further comprises the step of calculating location values of the hash values which authenticate the first digital document.

70. The method of claim 67, wherein the step of generating the certificate further comprises including a pointer to the secured item.

71. The method of claim 70, wherein the step of including the pointer further comprises including a time the secured item was secured.

72. The method of claim 58, further comprising the steps of:

a. a user performing the step of generating the request at a local location;

b. after the step of generating, the user transmitting the request to a service bureau;

c. before the step of combining, the service bureau receiving the request; and

d. the service bureau performing the steps of combining, hashing, and forming the repository.

73. The method of claim 72, further comprising:

a. the service bureau generating a certificate; and

b. the service bureau transmitting the certificate to the user.

74. A certificate providing a unique, self-verifying name to a first digital document, the certificate being generated by:

a. hashing the first digital document to generate a first hash value;

b. combining the first hash value with a second hash value dependent on at least one other digital document to generate a first combined value;

c. hashing the first combined value to generate a first combined hash value;

d. forming a repository of a plurality of hash values in the form of a directed acyclic graph having nodes, each node comprising a hash value dependent on at least one of said digital documents, the repository comprising a secure value derived from a hash value of at least one of said digital documents;

e. generating self-verifying hash values and associated location values in said repository for the first digital document; and

f. naming said first digital document using said location values to provide a self-verifying name for the first digital document.