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

摘要

Upon receiving a message {ID′_i−1, X′_i−1, m′_i−1, Y_i−1} from a signer (i−1), a signer _i generates a random number r_i, then calculates X_i=g^ri mod p using pieces of public information p, q and g, then sets X′_i=(X′_i−1, X_i), m′_i=(m′_i−1, m_i), then calculates e_i=f_i(X′_i, m′_i), d_i=h_i(X′_i, m′_i) with public one-way functions f_i and h_i, calculates y_i=(y_i−1+d_ir_i+e_is_i) mod q using a secret random number s_i, sets ID′_i=(ID′_i−1, ID_i), and sends information {ID′_i,X′_i,m′_i,y′_i} to the next signer (i+1). A verifier calculates e_i and d_i with the one-way functions f_i and h_i using X′_L and m′_L contained in received information {ID′_L, X′_L, m′_L, y_L}, and makes a check to see if g^yL≡X₁^d1 I_L^e1 . . . X_L^dL I_L^eL (mod p), thereby verifying signatures of the signers en bloc.