1. A method of 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) setting a predetermined bit number t to an integer equal to or greater than 1; (b) setting a maximum Hamming weight k to an integer equal to or greater than 0 and less than or equal to the predetermined bit number t, that is, 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; (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.