Combination in Advance Batch Multi-exponentiation on Elliptic Curve

摘要

Multi-exponentiation is very important in varies cryptographic and digital signatures.In the situation like electronic cash and SNS websites, the server need to answer a mass of requests in a short time. With every request,there are always processes of encryption,decryption, signature and verification. In these processes, there are large amount of computations of multi-exponentiation,which shows the demand of the acceleration of multi-exponentiation. Handling many multi-exponentiation simultaneously is called batch multi-exponentiation.Yang Sun first came up with a algorithm (BME) deal with this problem. We propose a new batch multi-exponentiation method to accelerate BME in this paper and also extend it to the elliptic curve setting by specifying an optimal left-to-right Binary signed-digit reeoding. It is named Combination in Advance Batch Multiexponentiation on Elliptic Curve (CABME)algorithm.We focus on the form which is multi-exponentiation with two bases in a group since it is commonly used. Our CABME algorithm is about 16.7% more effective than BME under the same situation.