Patent ID: 7496759

Claim:
A multisignature method implemented by a computer programmed as a multisignature generation apparatus which generates i-th signature σ i with respect to document data x based on i−1-th signature σ i−1 and document data x generated by another multisignature generation apparatus, the method comprising: dividing, by a processor of the computer, the i−1-th signature σ i−1 into two, and obtaining second partial data σ i−1,R of k 2 bits and remaining first partial data σ i−1,L ; generating random number data r i of k 0 bits; applying a first random function H i ′ to the first partial data σ i−1,L , the second partial data σ i−1,R , the random number data r i , and the document data x, and obtaining a first random function value w i of k 1 bits; applying a second random function G i to the first random function value w i , and obtaining a second random function value g i of (k 2 +k 0 ) bits; executing binary operation of the second random function value g i , the second partial data σ i−1,R ,and the random number data r i , and obtaining an operation result s i of (k 2 +k 0 ) bits; applying a signature generation function to data of k bits based on the operation result s i and the first random function value w i , and obtaining a signature value z i of k bits; concatenating the first partial data σ i−1,L to the signature value z i , and generating i-th signature σ i (=σ i−1,L ∥z i ); and outputting this i-th signature σ i .