Batch Blind Signatures on Elliptic Curves

Blind signature is a fundamental tool in electronic cash. In most existing blind signature schemes, both the signer and the verifier need to take expensive modular exponentiations. This situation is deteriorated in significant monetary transactions in which a large number of (multi-)exponentiations need to be calculated. This paper proposes batch blind signature to reduce the computation overheads at both the signer and the verifier sides in blind signatures on elliptical curves. To this end, we first propose a batch multi-exponentiation algorithm that allows a batch of multi-base exponentiations on elliptic curves to be processed simultaneously. We next apply our batch multi-exponentiation algorithm to speed up the Okamoto-Schnorr blind signature scheme in both the signing and the verification procedures. Specifically, the proposed algorithm is exploited for generating blind signatures so that multiple messages can be signed in a batch for sake of saving computation costs. The algorithm is further employed in the verification process, which gives a different batch signature verification approach from the existing batch verification algorithm. An attracting feature of our approach is that, unlike existing batch verification signature approach, our approach does distinguish all valid signatures from a batch purported signatures (of correct and erroneous ones). This is desirable in e-cash systems where a signature represents certain value of e-cash and any valid signature should not passed up. The experimental results show that, compared with acceleration with existing simultaneous exponentiation algorithm, our batch approach is about 55% and 45% more efficient in generating and verifying blind signatures, respectively.