Patent ID: 8078877

Claim:
A method for fast verifying a plurality of electronic signatures by batch-verifying a plurality of exponentiations when a set G and an element g belonging to the set G are given, the method comprising a processor performing the steps of: (a) setting a predetermined bit number t to an integer equal to or greater than 1; (b) setting a maximum Hamming weight k to is an integer equal to or greater than 0 and less than or equal to the predetermined bit number t, that, 0≦k≦t; (c) randomly selecting n verification exponents S i from a set of verification exponents S, where i is an integer such that 1≦i≦n, and the set of verification exponents S comprise elements whose bit values are less than or equal to the pre-determined bit value t and to which a Hamming weight less than or equal to the maximum Hamming weight k is allocated in an expansion of a number system, where n is a natural number; (d) computing a value of verification result by a predetermined verification formula to which the verification exponents are applied; and (e) checking whether the value of verification result satisfies a predetermined pass condition, and determining that the verification of the signatures is passed when the value of verification result satisfies the predetermined pass condition, wherein in (d), the predetermined verification formula comprises: ∏ i = 1 n ⁢ ⁢ y i s i = g ∑ i = 1 n ⁢ ⁢ x i ⁢ s i wherein x i ε Z, y i ε G, and Z denotes a natural number field.