Method for incremental authentication of documents

• US 20050091261A1
• Filed: 10/01/2004
• Published: 04/28/2005
• Est. Priority Date: 10/02/2003
• Status: Active Grant

• Current Assignee: Agency For Science Technology and Research (Government of Singapore)
• Original Assignee: Agency For Science Technology and Research (Government of Singapore)
• Inventors: Wu, Yong Dong, Deng, Huijie Robert
• Granted Patent: US 7,315,866 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of protecting an electronic document, the method comprising dividing an original document into data blocks; generating a corresponding hash value for each data block; generating a corresponding hash value for a group of data blocks (GOB); generating a hash tree structure based on the corresponding hash values for the data blocks and for the GOB; calculating a hash value of a root node of the hash tree structure, the root node having no parent in the hash tree structure; signing the hash value of the root node; and generating auxiliary authentication data; wherein said auxiliary authentication data enables authentication of portions of the electronic document based on a reconstruction of the hash tree structure.

Claims

1. A method of protecting an electronic document, the method comprising:

dividing an original document into data blocks;

generating a corresponding hash value for each data block;

generating a corresponding hash value for a group of data blocks (GOB);

generating a hash tree structure based on the corresponding hash values for the data blocks and for the GOB;

calculating a hash value of a root node of the hash tree structure, the root node having no parent in the hash tree structure;

signing the hash value of the root node; and

generating auxiliary authentication data;

wherein said auxiliary authentication data enables authentication of portions of the electronic document based on a reconstruction of the hash tree structure.

2. The method as claimed in claim 1, comprising:

dividing each data block into segments;

generating a corresponding incremental hash value for each segment of each data block;

wherein the generating of the hash tree structure is further based on the corresponding incremental hash values.

3. The method as claimed in claim 2, comprising:

assigning the hash value of each segment of each data block to a leaf node of the hash tree structure;

generating a value for a non-leaf node of the hash tree structure based on a compositional value of child nodes of said non-leaf node;

wherein the generating of the hash value for each data block is based on the value of a root node of a sub-tree of the hash tree structure having no parent in said sub-tree structure.

4. The method as claimed in claim 1, comprising:

assigning the hash value of each data block to a leaf node of the hash tree structure; and

generating a value for a non-leaf node of the hash tree structure based on a compositional value of child nodes of said non-leaf node.

5. The method as claimed in claim 1, wherein each leaf in the hash tree structure has a given priority within the hash tree structure, and the method comprises:

identifying portions of the electronic document corresponding to one or more leaves of the hash tree structure;

identifying the leaf node out of said one or more leaf nodes with the lowest priority in the hash tree structure;

generating a value for a sibling non-leaf node of said leaf node with the lowest priority based on a compositional value of child nodes of said non-leaf node;

wherein the generating of auxiliary authentication data is based on the value for said sibling non-leaf node.

6. The method as claimed in claim 1, comprising:

identifying portions of the electronic document corresponding to one or more leaves of the hash tree structure;

identifying a remainder of the hash tree structure;

wherein the generating of auxiliary authentication data is based on obtaining hash value information of the remainder of the hash tree structure through an incremental and commutative hash function.

7. The method as claimed in claim 6, wherein the incremental and commutative hash function is constructed by

selecting two large primes p and q;

denoting N=pq. A finite field Z*_N={x|gcd(x,N)=1, 1<

x<

N},

where gcd( ) is greatest common divisor;

selecting an element α

in field Z*_N and

wherein the hash value of the GOB is α

to the exponent of multiplicity of hash value V_i for each block in field Z*_N

8. The method as claimed in claim 1, wherein generating the hash value of the GOB comprises incorporating document identification information.

9. The method as claimed in claim 1, wherein the signing of the hash value of the root node of the hash tree structure comprises utilising RSA or DSS.

10. A method of authenticating an electronic document divided into a group of data blocks (GOB), the method comprising:

receiving a signature based on a hash value of a root node of an original hash tree structure representation of content of an original document, the root node having no parent in the original hash tree structure;

receiving auxiliary authentication data;

generating a corresponding hash value for each received data block;

generating a corresponding hash value for the received GOB;

reconstructing an authentication hash tree structure based on the corresponding hash values for the received data blocks and for the received GOB, and based on the received auxiliary authentication data; and

authenticating a hash value of a root node of the authentication hash tree structure with said received signature.

11. A system for protecting an electronic document, the system comprising:

a dividing means for dividing an original document into data blocks;

a hash value generating means for generating a corresponding hash value for each data block; and

for generating a corresponding hash value for a group of data blocks (GOB);

a hash tree structure generating means for generating a hash tree structure based on the corresponding hash values for the data blocks and for the GOB;

a processor means for calculating a hash value of a root node of the hash tree structure, the root node having no parent in the hash tree structure;

a signing means for signing the hash value of the root node; and

wherein the processor means further generates auxiliary authentication data, wherein said auxiliary authentication data enables authentication of portions of the electronic document based on a reconstruction of the hash tree structure.

12. A system for authenticating an electronic document divided into a group of data blocks (GOB), the system comprising:

a receiving means for receiving a signature based on a hash value of a root node of an original hash tree structure representation of content of an original document, the root node having no parent in the original hash tree structure and for receiving auxiliary authentication data;

a hash value generating means generating a corresponding hash value for each received data block and for generating a corresponding hash value for the received GOB;

a hash tree structure generating means for reconstructing an authentication hash tree structure based on the corresponding hash values for the received data blocks and for the received GOB, and based on the received auxiliary authentication data; and

a processor means for authenticating a hash value of a root node of the authentication hash tree structure with said received signature.

13. A computer readable data storage medium having stored thereon computer code means for instructing a computer to execute a method of protecting an electronic document, the method comprising:

dividing an original document into data blocks;

generating a corresponding hash value for each data block;

generating a corresponding hash value for a group of data blocks (GOB);

generating a hash tree structure based on the corresponding hash values for the data blocks and for the GOB;

calculating a hash value of a root node of the hash tree structure, the root node having no parent in the hash tree structure;

signing the hash value of the root node; and

generating auxiliary authentication data;

wherein said auxiliary authentication data enables authentication of portions of the electronic document based on a reconstruction of the hash tree structure.

14. A computer readable data storage medium having stored thereon computer code means for instructing a computer to execute a method of authenticating an electronic document divided into a group of data blocks (GOB), the method comprising:

receiving a signature based on a hash value of a root node of an original hash tree structure representation of content of an original document, the root node having no parent in the original hash tree structure;

receiving auxiliary authentication data;

generating a corresponding hash value for each received data block;

generating a corresponding hash value for the received GOB;

reconstructing an authentication hash tree structure based on the corresponding hash values for the received data blocks and for the received GOB, and based on the received auxiliary authentication data; and

authenticating a hash value of a root node of the authentication hash tree structure with said received signature.