Fast batch modular exponentiation with common-multiplicand multiplication

Abstract

In the field of asymmetric cryptography, the exponentiation operation that raises an element from a group to its power is fundamental for a great part of cryptosystems. The exponents are often large numbers which essentially lead to significant resource consumption for computation. There are two approaches to enhance the performance of exponentiation. One way is to improve the efficiency of multiplication itself. The other way is to reduce the number of multiplications that is required to perform exponentiation. In this thesis, we present an efficient algorithm for batch modular exponentiation which improves upon the previous generalized intersection method with respect to the cost of multiplications. The improvement is achieved by adopting an extended common-multiplicand multiplication technique that efficiently computes an arbitrary number of multiplications that share a common multiplicand at once. Our algorithm shows a better time-memory tradeoff compared to the previous generalized intersection method. We analyze the cost of multiplications and storage requirement of the proposed algorithm, and give an optimal parameter choice when the allowed amount of memory is sufficient or limited. The comparison shows that our algorithm reduces the cost of multiplications by 23% ∼ 41% when the number of input exponents is between 10 and 60, and the bit length of exponents is 1024, 2048 and 4096. The practical performance enhancement is also supported by the actual running time comparison. For further improvement, we also present an exponent ordering algorithm that rearranges the input exponents and a precomputation method to reduce the cost of multiplications.