| dc.description.abstract | Smart card and other stand-alone cryptographic devices provide a secure environment to store the secret key and manipulate sensitive information. However, those devices may suffer from the threat of side-channel analysis which exploits power consumption, execution time, or other side-channel leakages of those devices. Exponentiation computation is a basic operation in many modern public-key cryptosystems and also suffers from the threat of side-channel analysis. An attacker can retrieve the secret exponent by analyzing the leaked side-channel information. Since smart card usually has very limited memory capacity and computation capability, both space requirement and the immunity against side-channel analysis should be taken into consideration when designing fast exponentiation algorithms.
In this dissertation, we propose a series of multi-exponentiation algorithms which are developed based on the computational sequence of the binary GCD algorithm. Comparing with existing multi-exponentiation algorithms, the proposed algorithms have the advantage of space efficient, good performance, and being inversion free. They have the merit of developing countermeasures against side-channel analysis and are very suitable for implementation on smart card or other resource-limited devices. The proposed algorithms also have the advantage of good scalability, i.e., they achieve good performance in various bit lengths of exponents and various dimensions of multi-exponentiation.
We also develop and analyze exponentiation algorithms from the view point of exponent recoding. A generalization of the NAF recoding and the sliding window method is proposed. The proposed algorithm, a right-to-left ${0,1,r}$-NAF recoding, can cooperate with the Ha-Moon algorithm to achieve better immunity against differential power analysis. A detailed analysis of the left-to-right NAF recoding and the left-to-right sliding window method is also proposed. In contrast that the hidden Markov module cryptanalysis exploits multiple computational sequences and adapts to analyze randomized recoding algorithms, our analysis skill focuses on how much information can be retrieved by exploiting only one computational sequence and adapts to deterministic recoding algorithms. The proposed analysis clearly shows that the left-to-right exponent recoding is less secure than the right-to-left recoding.
| en_US |