摘要 |
<p>A fast batch verification method and apparatus are provided. In the method of batch- verifying a plurality of exponentiations, (a) a predetermined bit value t is set to an integer equal to or greater than 1 ; (b) a maximum Hamming weight k is set to an integer equal to or greater than 0 and less than or equal than the predetermined bit value t; (c) n verification exponents s <SUB>i</SUB> are randomly selected from a set of verification exponents S (n is an integer greater than 1, i is an integer such that l=i=n), where the set of verification exponents S include elements whose bit values are less than or equal to the predetermined bit value t and to which a Hamming weight less than or equal to the maximum Hamming weight k is allocated; (d) a value of verification result is computed by a predetermined verification formula; and (e) the verification of the signatures is determined to be passed when the value of verification result satisfies a pre¬ determined pass condition. Accordingly, it is possible to significantly reduce the amount of computation and particularly, the computation amount of multiplication, without increasing a probability that a verification error would occur, thereby significantly improving the speed of verifying a plurality of signatures.</p> |