Fast batch verification method and apparatus there-of

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 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 Si 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 (a) comprises setting the predetermined bit value t to be equal to or greater than a security parameter 1
• wherein (b) comprises setting the maximum Hamming weight k to a minimum integer satisfying:
• ∑
• i
• =
• 1
• k
• ⁢
• ⁢
• (
• t
• i
• )
• ≥
• 2
• l
• .