Fast exponentiationaAlgorithms using bah and multi-exponentiation techniques

Abstract

Public key cryptosystems often involve raising elements of some group (e.g., $\\\\mathbb{Z}/N\\\\mathbb{Z}$, $\\\\mathbb{F}_{2^n}$, or elliptic curves) to large powers. Such exponentiation can be time-consuming and is often the dominant part of modern cryptographic algorithms for encryption, key exchange, digital signatures, and authentication. An important question is how fast this exponentiation can be done, which often determines whether a given system is practical especially in resource-limited environments. The best method for exponentiation depends strongly on the group being used, the hardware the system is implemented on, and whether one element is being raised repeatedly to different powers, different elements are raised to a fixed power, or both powers and group elements vary. In this thesis, we focus on the ways to reduce effectively the number of group operations needed to perform exponentiation in the case that both powers and group elements vary. In some algebraic structures, the computation of a large exponentiation can be reduced to a product of small exponentiations. If an abelian group $G$ admits an appropriate endomorphism $\\\\phi$ then the single exponentiation $x^E$ can be transformed into $x^{E_0} \\\\cdot {\\\\phi (x)}^{E_1} \\\\cdots {\\\\phi^{d-1}(x)}^{E_{d-1}}$ for suitable integers $E_0,E_1 \\\\ldots, E_{d-1}$ which in many practical instances have size $O(E^{1/d})$. Fortunately, elliptic curves provide various efficient endomorphisms such as the Frobenius endomorphism. The endomorphism used in exponent-folding techniques is a special case. Instead of computing each exponentiation separately and then multiplying them, computing them in a batch or simultaneously shows very good performance. Base-$\\\\phi$ expansion methods based on the Frobenius endomorphism is known to be the most efficient approach in terms of reducing the elliptic curve operations. In this thesis, we propose three efficient exponentiation algorithms. The f...