Distributed digital signature generation method and digitally signed digital document generation method and apparatus

• US 7,174,460 B2
• Filed: 02/22/2002
• Issued: 02/06/2007
• Est. Priority Date: 02/22/2001
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Horita, Eiichi, Ono, Satoshi
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): HENEGHAN, MATTHEW E
• Application Number:
  US10/080,647
• Publication Number:
  US 20020152389A1
• Time in Patent Office: 1,810 Days
• Field of Search: 713/180, 713/176, 380/286
• US Class Current: 713/176
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

In a distributed digital signature generation method, the method includes the steps of: generating partial signature keys by distributed processes, generating partial digital signatures by using the partial signature keys for the hash value of an input digital document to which additional information such as time is added, combining a predetermined threshold number of partial digital signatures, performing a transformation process on the partial digital signatures according to the combination, and generating an integrated digital signature from the result of the transformation process, in which a least common multiple of predetermined values is used as a transformation number, and it is judged whether an incorrect partial digital signature exists and the number is one, and the incorrect partial digital signature is identified when the number is one.

Claims

1. A distributed digital signature generation method for generating a digital signature for a digital document (M) by using a plurality of partial digital signature generation parts, said distributed digital signature generation method comprising:

a partial digital signature generation step in which each of said partial digital signature generation parts generates a partial signature key by communicating with each other without using a trusted third party, generates a partial digital signature by using said partial signature key for a hash value (H(M)) of an input digital document (M), and outputs said partial digital signature or a pair of said digital document and said partial digital signature;

a partial digital signature number set selecting step of assigning one of numbers from 1 to m to each of said partial digital signatures wherein m is the number of said partial digital signatures, selecting a number set I(i) including numbers ((i−

1) mod m)+1,((i−

1+1) mod m)+1, . . . ,((i−

1+(k−

1)) mod m)+1 for each of i=1, . . . , m, wherein k is a threshold necessary for generating an integrated digital signature;

an integrated digital signature generating step of combining said partial digital signatures S(i(1), M), . . . , S(i(k), M) to generate said integrated digital signature S(I(i), M) for each of i=1, . . . , m wherein S(i, M) indicates a partial digital signature to which i is assigned and wherein elements of said number set I(i) are i(1), . . . , i(k),

wherein said integrated digital signature generating step includes;

a signature verification step of performing a signature verification process for said integrated digital signature S(I(i), M) for each of i=1, . . . , m to determine whether said integrated digital signature S(I(i), M) is a correct digital signature for H(M);

an incorrect partial digital signature existence determination step of determining that no incorrect partial digital signature exists in said partial digital signatures S(i, M) (i=1, . . . , m) if S(I(i), M) is determined to be a correct digital signature for H(M) for every i=1, . . . , m, and determining that at least an incorrect partial digital signature exists if at least one of S(I(i), M) (i=1, . . . , m) is determined to be incorrect;

an incorrect partial digital signature specifying step, performed when it is determined that at least one incorrect partial digital signature exists, of determining whether a set F of i=1, . . . , m agrees with a set F(j) (j is one of 1, . . . , m), wherein said set F is defined to be the set of i=1, . . . , m such that S(I(i), M) is incorrect for H(M), and wherein said set F(j) is the set of i=1, . . . , m by which said number set I(i) includes j, and determining that the number of said incorrect partial digital signature is only one if there is only one j by which F agrees with said set F(j), and if not, determining that the number of said incorrect partial digital signatures is equal to or greater than 2, and further, when it is determined that the number of said incorrect partial digital signature is only one, determining said only one j by which F agrees with F(j) so as to specify that said only one incorrect partial digital signature is S(j, M); and

said distributed digital signature generation method further comprising a result output step of;

when it is determined that no incorrect partial digital signature exists, outputting a determination result indicating that no incorrect partial digital signature exists and said integrated digital signature determined to be correct in said signature verification step;

when it is determined that only one incorrect partial digital signature exists, outputting a determination result indicating that only one incorrect partial digital signature exists, identification information of said only one incorrect partial digital signature, and said integrated digital signature determined to be correct in said signature verification step;

when it is determined that the number of said incorrect partial digital signatures is equal to or greater than 2, outputting a determination result indicating that the number of said incorrect partial digital signatures is equal to or greater than 2.

2. A digitally signed digital document generation method for generating a digital document with a digital signature comprising the distributed digital signature generation method as claimed in claim 1, and further comprising the step of:

generating a digital document with digital signature which includes said digital document and said integrated digital signature.

3. A computer readable medium storing a program for causing a computer to generate a digital signature for a digital document by using a plurality of partial digital signature generation parts, comprising:

each of said partial digital signature generation parts generates a partial signature key by communicating with each other without using a trusted third party, generates a partial digital signature by using said partial signature key for a hash value (H(M)) of an input digital document (M), and outputs said partial digital signature or a pair of said digital document and said partial digital signature;

said program comprising;

integrated digital signature generating program code means for assigning one of numbers from 1 to m to each of said partial digital signatures wherein m is the number of said partial digital signatures, selecting a number set I(i) including numbers ((i−

1) mod m)+1, ((i−

1+1) mod m)+1, . . . , ((i−

1+(k−

1)) mod m)+1 for each of i=1, . . . , m, wherein k is a threshold necessary for generating an integrated digital signature; and

for combining said partial digital signatures S(i(1), M), . . . , S(i(k), M) to generate said integrated digital signature S(I(i), M) for each of i=1, . . . , m wherein S(i, M) indicates a partial digital signature to which i is assigned and wherein elements of said number set I(i) are i(1), . . . , i(k),

wherein said integrated digital signature generating program code means includes;

signature verification program code means for performing a signature verification process for said integrated digital signature S(I(i), M) for each of i=1, . . . , m to determine whether said integrated digital signature S(I(i), M) is a correct digital signature for H(M);

incorrect partial digital signature existence determination program code means for determining that no incorrect partial digital signature exists in said partial digital signatures S(i, M) (i=1, . . . , m) if S(I(i), M) is determined to be a correct digital signature for H(M) for every i=1, . . . , m, and determining that at least an incorrect partial digital signature exists if at least one of S(I(i), M) (i=1, . . . , m) is determined to be incorrect;

incorrect partial digital signature specifying program code means for, when it is determined that at least one incorrect partial digital signature exists, determining whether a set F of i=1, . . . , m agrees with a set F(j) (j is one of 1, . . . , m), wherein said set F is defined to be the set of i=1, . . . , m such that S(I(i), M) is incorrect for H(M), and wherein said set F(j) is the set of i=1, . . . , m by which said number set I(i) includes j, and determining that the number of said incorrect partial digital signature is only one if there is only one j by which F agrees with said set F(j), and if not, determining that the number of said incorrect partial digital signatures is equal to or greater than 2, and further when it is determined that the number of said incorrect partial digital signature is only one, determining said only one j by which F agrees with F(j) so as to specify that said only one incorrect partial digital signature is S(j, M); and

said program further comprising result output program code means for;

when it is determined that no incorrect partial digital signature exists, outputting a determination result indicating that no incorrect partial digital signature exists and said integrated digital signature determined to be correct in said signature verification step;

when it is determined that only one incorrect partial digital signature exists, outputting a determination result indicating that only one incorrect partial digital signature exists, identification information of said only one incorrect partial digital signature, and said integrated digital signature determined to be correct in said signature verification step;

when it is determined that the number of said incorrect partial digital signatures is equal to or greater than 2, outputting a determination result indicating that the number of said incorrect partial digital signatures is equal to or greater than 2.