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

Abstract

Upon receiving a message {ID′,, X′,, m′,, Y,} from a signer (i−1), a signer,generates a random number r,, then calculates X,=g,mod p using pieces of public information p, q and g, then sets X′,=(X′,, X,), m′,=(m′,, m,), then calculates e,=f,(X′,, m′,), d,=h,(X′,, m′,) with public one-way functions f,and h,, calculates y,=(y,+d,r,+e,s,) mod q using a secret random number s,, sets ID′,=(ID′,, ID,), and sends information {ID′,,X′,,m′,,y′,} to the next signer (i+1). A verifier calculates e,and d,with the one-way functions f,and h,using X′,and m′,contained in received information {ID′,, X′,, m′,, y,}, and makes a check to see if g,≡X,I,. . . X,I,(mod p), thereby verifying signatures of the signers en bloc.