## 4 Double-Base Chains with Point Halving: Theory and Algorithms  
Double-base chains (DBCs) offer an advanced method for representing scalar values as a sum of terms, each of which is a product of powers of two or more distinct bases. The classical double-base number system (DBNS) represents integers using sums of the form \(2^{a}3^{b}\). This approach reduces the number of required additions during scalar multiplication by allowing a more compact representation of scalars. The innovation proposed by [27] refines this further by replacing the use of base 2 with base \(\frac{1}{2}\), thus enabling point halving instead of point doubling. The representation becomes:  
\[k=\sum_{i=1}^{m}s_{i}\left(\frac{1}{2}\right)^{b_{i}}\cdot 3^{t_{i}}, \tag{4}\]  
where \(s_{i}\in\{-1,+1\}\), \(b_{i}\), and \(t_{i}\) are integer exponents, and the exponents are chosen such that \(\{b_{i}\}\) is strictly increasing and \(\{t_{i}\}\) is decreasing. This form is termed a \"double-base chain\" because the sequence of operations forms a chain of scalar updates through halving and tripling. The primary benefit of this representation is the replacement of expensive point-doubling operations with point halving, which is computationally cheaper, especially over binary fields. This method is particularly effective for devices that operate over fields \(\mathbb{F}_{2^{m}}\), where field arithmetic is optimized for bitwise operations. Point Halving AlgorithmTo perform point halving over \(\mathbb{F}_{2^{m}}\), one typically solves the elliptic curve equation in reverse. For a curve of the form \(y^{2}+xy=x^{3}+ax^{2}+b\), given a point \(Q=(x_{Q},y_{Q})=2P\), the halving process recovers \(P=(x_{P},y_{P})\) by solving:  
\[\lambda=x_{P}+\frac{y_{Q}}{x_{Q}}\qquad\text{(if $x_{Q}\
eq 0$)} \tag{5}\]  
\[x_{P}=\sqrt{x_{Q}+\lambda^{2}+a} \tag{6}\]  
\[y_{P}=x_{P}\cdot(\lambda+1) \tag{7}\]  
Solving for \(x_{P}\) and \(y_{P}\) requires solving quadratic equations in \(\mathbb{F}_{2^{m}}\), which is efficient due to the structure of binary fields. This makes point halving particularly attractive in these settings, as it avoids costly field inversions typically required for point doubling. When applying the DBC method in scalar multiplication, the scalar \(k\) is represented as a sum of signed terms of the form \(s_{i}\cdot(\frac{1}{2})^{b_{i}}\cdot 3^{t_{i}}\). Rather than computing each term independently, we use a left-to-right accumulation approach. Starting from an initial point, we iteratively apply tripling and halving operations to build the final result. This method minimizes redundant computation and allows efficient reuse of intermediate values. A revised high-level description of scalar multiplication using DBC with point halving is as follows:  
1. Compute the DBC representation of the scalar \(k\) a sequence of signed terms \(s_{i}\cdot(\frac{1}{2})^{b_{i}}\cdot 3^{t_{i}}\). 2. Initialize the result \(R=\mathcal{O}\) (the point at infinity). 3. Initialize a working point \(Q=P\). 4. For each term in the DBC sequence (from most to least significant): * Apply \(t_{i}\) successive tripling operations to \(Q\). * Apply \(b_{i}\) successive point halvings to \(Q\). * If \(s_{i}=-1\), set \(Q\leftarrow-Q\). * Add \(Q\) to the result: \(R\gets R+Q\). 5. Return \(R\) as the final result \(kP\). In \(\mathbb{F}_{2^{m}}\), point halving can be significantly faster than doubling because it avoids or simplifies field inversions. It typically involves solving quadratic equations or computing square roots, which are more efficient in binary fields. Thus, halving offers a concrete computational advantage over doubling, justifying its use in our scalar multiplication scheme. Compared to binary or windowed methods, this approach offers
* Fewer overall elliptic curve operations. * Substantial reduction in field inversions and multiplications. * Improved side-channel resistance due to less predictability in operation patterns.