A note on asynchronous multi-exponentiation algorithm using binary representation

A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-exponentiation in a certain finite multiplication group. In 2007, Yang et al. presented an interesting asynchronous multi-exponentiation algorithm called the ^SUt method, which uses the binary representations for the exponents. In this note, we analyze the computational efficiency of the ^SUt method by modeling the scanning process as a Markov chain. It shows that their computational efficiency result is incorrect. Moreover, we make a performance comparison among the published techniques and show that the performance of a modified sliding window method is better than that of the ^SUt method, when there are 4 or more additional registers. We hope that our research will be convenient to the development of the cryptographic devices.