Method and apparatus for en-bloc verification of plural digital signatures and recording medium with the method recorded thereon

A method whereby a verifier verifies en bloc digital signatures attached by signers i to an electronified document m′i, where i=1, 2, . . . , L, said L being an integer equal to or greater than 2, information containing a parameter q for each of said signer i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 by the use of said parameter q being published in advance, said method comprising the steps:

• wherein said each signer i:
• (a) generates a first random number si as secret information, then generates information Ii=G2(si, β) with a function G2 through the use of a public parameter β and said first random number si, and publishes said information Ii and two one-way functions fi and hi and identification information IDi used by the signer i as his public information {IDi, Ii, fi, hi};
• (b) generates a second random number ri, then generates information Xi=Φ(ri, β)by setting said parameter β and said second random number ri in a function Φ, and sets information containing the information Xi as X′i;
• (c) generates
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• with said one-way functions fi and hi through the use of document information m′i containing a document mi to be signed and said information X′i;
• and
• (d) generates, for information containing ei, di, si and ri, a signature
• yi=Sgi(ei, di, si, ri)
• with a signature function Sgi generated using said parameter q and, sending out information {ID′i, X′i, m′i, yi}, containing said identification information IDi as identification information ID′i to a verifier as a final destination:
• and
• wherein said verifier:
• (e) computes, from said public information {IDi, Ii, fi, hi}, information Ii corresponding to said identification IDi contained in said information ID′i in the received information {ID′i, X′i, m′i, yi} and said one-way functions fi and hi, and calculates ei and di using said one-way functions fi and hi and said received pieces of information X′i and m′i;
• (f) calculates said information Xi contained in said information X′i, and computes
• Z′=V((Xi*di), (Ii*ei)|i=1, . . . , L)
• with a function V containing calculations (Xi*di) of said di and said Xi and (Ii*ei) of said ei and said Ii for i=1, . . . , L;
• and
• (g) computes W=Γ(Y*β) with a function Γ containing a calculation (Y*β) using β and an accumulated value Y of y1 to yL, then makes a check to see if W=Z′, and if both values match each other, decides that said signatures are all valid.

A signer apparatus for a system in which each of a series of signers i=1, . . . , L, L being an integer equal to or greater than 2, attaches a digital signature to an electronified document m′i and a verifier verifies said digital signatures en bloc, wherein said, information containing a parameter q for each of said signers i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 by the use of said parameter q are published in advance, said signer apparatus comprising:

• storage means for storing said public parameters q and β of said system, identification information IDi of said each signer i and a first random number si as his secret information;
• function G2 means for generating information Ii=G2(si, β) with a function G2 through the use of said public parameter β and said first random number si, said information Ii being published as signer public information {IDi, Ii, fi, hi} together with a pair of one-way functions fi and hi and identification information IDi that said each signer i uses;
• random generator means for generating a second random number ri;
• function Φ means for setting said parameter β and said second random number ri in a function Φ to generate information Xi=Φ(ri, β);
• a pair of one-way function means for generating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• with said pair of one-way functions fi and hi through the use of document information m′i containing a document in to be signed and information X′i containing said information Xi;
• signature function means for generating, for information containing ei, di, si, ri and yi−1, a signature
• yi=Sgi(ei, di, si, ri, yi−1)
• with a signature function Sgi generated using said parameter q;
• and
• means for sending information {ID′i, X′i, m′i, yi}, as information containing said identification information IDi, to the next signer (i+1) in a series of signers 1 to L, the last signer L sending the information {ID′L, X′L, m′L, yL} to a verifier as a final destination.

A signer apparatus for a system in which each of signers i=1, . . . , L, said L being an integer equal to or greater than 2, attaches a digital signature to an electronified document m′i and a verifier verifies said digital signatures en bloc, wherein said information containing a parameter q for each of said signers i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 by the use of said parameter q are published in advance, said signer apparatus comprising:

• storage means for storing said public parameters q and β of said system, identification information IDi of said each signer i and a first random number si as his secret information;
• function G2 means for generating information Ii=G2(si, β) with a function G2 through the use of said public parameter β and said first random number si, said information Ii being published as signer public information {IDi, Ii, fi, hi} together with a pair of one-way functions fi and hi and identification information IDi that said each signer i uses;
• random generator means for generating a second random number ri;
• function Φ means for setting said parameter β and said second random number ri in a function Φ to generate information Xi=Φ(ri, β);
• a pair of one-way function means for generating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• with said pair of one-way functions fi and hi through the use of document information m′i containing a document mi to be signed and information X′i containing said information Xi,
• signature function means for generating, for information containing ei, di, si and ri, a signature
• yi=Sgi(ei, di, si, ri)
• with a signature function Sgi generated using said parameter q;
• and
• means for sending information {ID′i, X′i, m′i, yi}, as information containing said identification information IDi to a verifier.

A verifier apparatus for a system in which each of a series of signers i=1 to L, L being an integer equal to or greater than 2, attaches a digital signature to an electronified document m′i and a verifier verifies the digital signatures of the signers en bloc, wherein information containing a parameter q for each of said signers, i, to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 by the use of said parameter q are published in advance, said verifier apparatus comprising:

• a pair of one-way function means for obtaining, from public information {IDi, Ii, fi, hi}, information Ii corresponding to identification information IDi contained in ID′L in information {ID′L, X′L, m′L, yL} received from the last one, L, of the series of signers and one-way functions fi and hi, and for calculating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• through the use of said one-way functions fi and hi and information X′i and m′i contained in said received pieces of information X′L and m′L;
• function V means for obtaining Xi in said information X′i and for calculating
• Z′=V((Xi*di), (Ii*ei)|i=1, . . . , L)
• through the use of a function V containing a calculation (Xi*di) of di and Xi and a calculation (Ii*ei) of ei and Ii;
• function Γ means for obtaining W=Γ(yi*β) by a function Γ containing a calculation (yi*β) of yi and β;
• and
• comparison means supplied with said Z′ and W, for making a check to see if they match each other, and if they match each other, providing an output indicating that said received document (m1, . . . , mL) have been duly signed by L signer i apparatuses.

A verifier apparatus for a system in which each of signers i=1 to L, L being an integer equal to or greater than 2, attaches a digital signature to an electronified document m′i and a verifier verifies the digital signatures of the signers en bloc, wherein information containing a parameter q for each of said signers, i, to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 by the use of said parameter q are published in advance, said verifier apparatus comprising:

• a pair of one-way function means for obtaining, from public information {IDi, Ii, fi, hi} information Ii corresponding to identification information IDi contained in ID′i in information {ID′i, X′i, m′i, yi} received from each of said signers, i, and one-way functions fi and hi, and for calculating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• through the use of said one-way functions fi and hi and said received pieces of information X′i and m′i;
• function V means for obtaing Xi in said information X′i and for calculating
• Z′=V((Xi*di), (Ii*ei)|i=1, . . . , L)
• through the use of a function V containing a calculation (Xi*di) of di and Xi and a calculation (Ii*ei) of ei and Ii;
• function Γ means for obtaining W=Γ(Y*β) by a function Γ containing a calculation (Y*β) using β and an accumulated value Y of y1 to yL;
• and
• comparison means supplied with said Z′ and W, for making a check to see if they match each other, and if they match each other, providing an output indicating that said received document (m1, . . . , mL) have been duly signed by L signer i apparatuses.

A recording medium for a signer apparatus which has recorded thereon a program which is used in said signer apparatus in a system in which:

• each of a series of signers, i, attaches a digital signature to an electronified document m′i and a verifier verifies said digital signatures en bloc;
• i=1, . . . , L, L being an integer equal to or greater than 2;
• information containing a parameter q for each signer i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 through the use of said parameter q is published in advance;
• and information Ii=G2(si, β) pregenerated by said each signer i using said public parameter β and a secret random number si, a pair of one-way functions fi and hi for use by said each signer i and identification information IDi are published as signer public information {IDi, Ii, fi, hi} in advance;
• said program comprising the steps of:
• (a) generating a second random number ri;
• (b) setting said parameter β and said second random number ri in a function Φ to generate information Xi=Φ(ri, β);
• (c) generating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• with said one-way functions fi and hi through the use of document information m′i containing said document mi to be signed and said information X′i containing said information Xi;
• (d) generating, for information containing ei, di, si, ri and yi−1, a signature
• yi=Sgi(ei, di, si, ri, yi−1)
• with a signature function Sgi generated using said parameter q;
• and
• (e) sending information {ID′i, X′i, m′i, yi}, containing said identification information IDi as identification information ID′i, to the next signer (i+1), the last signer L sending the information {ID′L, X′L, m′L, m′L, yL} to a verifier as a final destination.

A recording medium for a signer apparatus which has recorded thereon a program which is used in said signer apparatus in a system in which:

• each of signers, i, attaches a digital signature to an electronified document m′i and a verifier verifies said digital signatures en bloc;
• i=1, . . . , L, L being an integer equal to or greater than 2;
• information containing a parameter q for each signer i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 through the use of said parameter q is published in advance;
• and information Ii=G2(si, β) pregenerated by said each signer i using said public parameter β and a secret random number si, a pair of one-way functions fi and hi for use by said each signer i and identification information IDi are published as signer public information {IDi, Ii, fi, hi} in advance;
• said program comprising the steps of:
• (a) generating a second random number ri;
• (b) setting said parameter β and said second random number ri in a function Φ to generate information X1=Φ(ri, β);
• (c) generating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• with said one-way functions fi and hi through the use of document information m′i containing said document mi to be signed and said information X′i, containing said information Xi;
• (d) generating, for information containing ei, di, si, and ri, a signature
• yi=Sgi(ei, di, si, ri)
• with a signature function Sgi generated using said parameter q;
• and
• (e) sending information {ID′i, X′i, m′i, yi}, containing said identification information IDi as identification information ID′i, to a verifier.

A recording medium for a verifier apparatus which has recorded thereon a program which is used in said verifier apparatus in a system in which:

• each of a series of signers, i, attaches a digital signature to an electronified document m′i and a verifier verifies said digital signatures en bloc;
• i=1, . . . , L, L being an integer equal to or greater than 2;
• and information containing a parameter q for each signer i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 through the use of said parameter q is published in advance;
• said program comprising the steps of:
• (a) obtaining, from public information {IDi, Ii, fi, hi}, information Ii corresponding to identification information IDi contained in ID′i in information {ID′L, X′L, m′L, yL} received from the last signer L of the series of said signers and one-way functions fi and hi, and calculating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• through the use of said one-way functions fi and hi and information X′i and m′i contained in said received pieces of information X′L and m′L;
• (b) obtaining Xi in said information X′i and calculating
• Z′=V((Xi*di), (Ii*ei)|i=1, . . . , L)
• by a function V containing a calculation (Xi*di) of di and Xi and a calculation (Ii*ei) of ei and Ii;
• (c) obtaining W=Γ(y1*β) by a function Γ containing a calculation (yi*β) of yi and β;
• and
• (d) receiving said values Z′ and W, then making a check to see if they match each other, and if they match each other, providing an output indicating that said received documents (m1, . . . , mL) have been duly signed by L signers.

A recording medium for a verifier apparatus which has recorded thereon a program which is used in said verifier apparatus in a system in which:

• each of signers, i, attaches a digital signatures to an electronified document m′i and a verifier verifies said digital signatures en bloc;
• i=1, . . . L, L being an integer equal to or greater than 2;
• and information containing a parameter q for each signer i to generate a signature function Sgi and a parameter β=G1(q) obtained with a function G1 through the use of said parameter q is published in advance;
• said program comprising the steps of:
• (a) obtaining, from public information {IDi, Ii, fi, hi}, information Ii corresponding to identification information IDi contained in ID′i in information {ID′i, X′i, m′i, yi} received from each of said signers, i, and one-way functions fi and hi, and calculating
• ei=fi(X′i, m′i)
• di=hi(X′i, m′i)
• through the use of said one-way functions fi and hi and said received pieces of information X′i and m′i;
• (b) obtaining Xi in said information X′i and calculating
• Z′=V((Xi*di), (Ii*ei)|i=1, . . . , L)
• by a function V containing a calculation (Xi*di) of di and Xi and a calculation (Ii*ei) of ei and Ii;
• (c) obtaining W=Γ(Y*β) by a function Γ containing a calculation (Y*β) using β and an accumulated value Y of y1 to yL;
• and
• (d) receiving said values Z′ and W, then making a check to see if they match each other, and if they match each other, providing an output indicating that said received documents (m1, . . . , mL) have been duly signed by L signer i apparatuses.