| |
| A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-scalar multiplication in a certain finite additive group defined by an elliptic curve. In this paper, we propose an adaptive window method for the multi-scalar multiplication, which can balance the computation cost and the memory cost under the resource-constrained environments. By modeling the scanning process as a Markov chain, we analyze the computational efficiency of this adaptive window method using the non-adjacent form (NAF) representation. When there are 2-4 extra registers, the adaptive window method using the NAF representation on average requires 11%-19% fewer additions than the Shamir trick using the joint sparse form (JSF) representation. In order to reduce the number of required registers, our strategy in the adaptive window method is not to store all values of the possible block pairs in the certain representations of two integers, but only to store those values with high probabilities. |
|
| Keywords:Public-key cryptosystem; Multi-scalar multiplication; Adaptive window method; Non-adjacent form (NAF) representation; Markov chain; Resource-constrained environment |
|
