1.
$$
\begin{align*}
f(P,Q) &= f_P(P+Q+A) - (2Q+A) \\
\ell(P) &= -(P+A)
\end{align*}
$$

where $f_P \neq 0, 2$, producing (after memoization of one doubling in R) Algorithm 15, and:

2.
$$
\begin{align*}
f(P,Q) &= P + Q \\
\ell(P) &= P + A
\end{align*}
$$

producing Algorithm 5 p.7.

Note that the second solution is actually the common Montgomery ladder for the scalar multiplication (Subsection 2.4). It was automatically generated in [11] by solving the ladder equations, confirming that our solutions are generalizations of the Montgomery ladder.

Note also that in the first solution there is no constraint on $f_P$, which thus can be randomly generated (Line 3) in $\mathbb{F}_p$ while satisfying constraints from Theorem 4. As in Subsection 5.2, this provides a blinding integer which hinders advanced side-channel attacks like CPA [10]. Because $R$ depends only on $f_P$ and $A$, it can be precomputed before the loop (Line 4). We discuss in Subsection 6.4 the feasibility and performance of the scalar multiplications by $f_P$ involved in the algorithm.

Finally, note that the case $f_P = 1$ corresponds to the ladder function $f(P,Q) = P - Q$, similar to the Montgomery ladder except that the point $Q$ has an opposite sign.

## 6.3 Fully-Interleaved Ladder Solution

In this subsection we solve the ladder equations in the fully-interleaved case. Remain two equations. In the case $\ell_P = -1$, Equation (2a) $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the fully-interleaved ladders is equivalent to:

$$ \begin{cases} 2g_P - g_Q = -2 \\ g_P - g_Q + g_A = -2 \end{cases} $$

So $g_Q = 2(1 + g_P)$ and $g_A = g_P$. Thus, Equation (2d) $g(f(\ell(x), x), x) = \varepsilon(x)$ for the fully-interleaved ladders implies that $f_P g_P = 0$. Because we assumed $f_P, g_P \neq 0$ and we look for a solution independent from the chosen field for the coefficients, we have no solution for this case.

**Algorithm 15 Semi-Interleaved Ladder for the Scalar Multiplication**

**input** public $p, A$; secret $k$

1: $P \leftarrow \mathcal{O}$

2: $Q \leftarrow -A$

3: $f_P \leftarrow \text{random}(\mathbb{F}_p \setminus \{0, 2\})$

4: $R \leftarrow (f_P - 1)A$

5: **for** $i = d$ **to** 0 **do**

6: **if** $k[i] = 1$ **then**

7: $S \leftarrow 2Q$

8: $P \leftarrow f_P(P+Q) + R - S$

9: $Q \leftarrow S$

10: **else**

11: $S \leftarrow 2P$

12: $Q \leftarrow f_P(Q + P) + R - S$

13: $P \leftarrow S$

14: **end if**

15: **end for**

16: **return** $P$

**output** $P = kA$

In the case $\ell_P = 1$, Equation (2a) $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the fully-interleaved ladders is equivalent to:

$$ \begin{cases} 2g_P + g_Q = 2 \\ g_P + \frac{g_Q}{3 - 2f_P} + g_A = 1 + \frac{1}{3 - 2f_P} \end{cases} $$

So $g_Q = 2(1 - g_P)$ and $g_A = 1 + \frac{(2f_P - 1)g_P - 1}{3 - 2f_P}$. Thus Equation (2d) $g(f(\ell(x), x), x) = \varepsilon(x)$ for the fully-interleaved ladders implies that $\frac{2(f_P(g_P - 1) + 1)}{3 - 2f_P}A = \mathcal{O}$. To avoid constraint on $A$, we assume $f_P(g_P - 1) + 1 = 0$; i.e., $g_P = 1 - \frac{1}{f_P}$.

**Theorem 5.** The double-and-add algorithm with $\theta(P) = 2P + A$ and $\varepsilon(P) = 2P$ is fully-ladderizable with:

$$ f(P,Q) = f_P \left( P - Q - \frac{1}{3-2f_P} A \right) + 2Q + \frac{1}{3-2f_P} A $$

$$ g(P,Q) = P + \frac{1}{f_P} \left( -P + 2Q + \frac{1}{3-2f_P} A \right) - \frac{1}{3-2f_P} A $$

$$ \ell(P) = P + \frac{1}{3-2f_P} A $$

where $f_P \neq 0, 1, 2$, and where $f_P$ and $3 - 2f_P$ are invertible, producing (after memoization in R and S) Algorithm 16.

Note that, because the coefficients are chosen in $\mathbb{F}_p$ with $p$ prime, if $f_P \neq 0$ and $f_P \neq 3 \times 2^{-1}$, then $f_P$ and $3 - 2f_P$ are invertible. Hence, $f_P$ can be
1.
$$
\begin{align*}
f(P,Q) &= f_P(P+Q+A) - (2Q+A) \\
\ell(P) &= -(P+A)
\end{align*}
$$

where $f_P \neq 0, 2$, producing (after memoization of one doubling in R) Algorithm 15, and:

2.
$$
\begin{align*}
f(P,Q) &= P + Q \\
\ell(P) &= P + A
\end{align*}
$$

producing Algorithm 5 p.7.

Note that the second solution is actually the common Montgomery ladder for the scalar multiplication (Subsection 2.4). It was automatically generated in [11] by solving the ladder equations, confirming that our solutions are generalizations of the Montgomery ladder.

Note also that in the first solution there is no constraint on $f_P$, which thus can be randomly generated (Line 3) in $\mathbb{F}_p$ while satisfying constraints from Theorem 4. As in Subsection 5.2, this provides a blinding integer which hinders advanced side-channel attacks like CPA [10]. Because $R$ depends only on $f_P$ and $A$, it can be precomputed before the loop (Line 4). We discuss in Subsection 6.4 the feasibility and performance of the scalar multiplications by $f_P$ involved in the algorithm.

Finally, note that the case $f_P = 1$ corresponds to the ladder function $f(P,Q) = P - Q$, similar to the Montgomery ladder except that the point $Q$ has an opposite sign.

## 6.3 Fully-Interleaved Ladder Solution

In this subsection we solve the ladder equations in the fully-interleaved case. Remain two equations. In the case $\ell_P = -1$, Equation (2a) $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the fully-interleaved ladders is equivalent to:

$$ \begin{cases} 2g_P - g_Q = -2 \\ g_P - g_Q + g_A = -2 \end{cases} $$

So $g_Q = 2(1 + g_P)$ and $g_A = g_P$. Thus, Equation (2d) $g(f(\ell(x), x), x) = \varepsilon(x)$ for the fully-interleaved ladders implies that $f_P g_P = 0$. Because we assumed $f_P, g_P \neq 0$ and we look for a solution independent from the chosen field for the coefficients, we have no solution for this case.

**Algorithm 15 Semi-Interleaved Ladder for the Scalar Multiplication**

**input** public $p, A$; secret $k$

1: $P \leftarrow \mathcal{O}$

2: $Q \leftarrow -A$

3: $f_P \leftarrow \text{random}(\mathbb{F}_p \setminus \{0, 2\})$

4: $R \leftarrow (f_P - 1)A$

5: **for** $i = d$ **to** 0 **do**

6: **if** $k[i] = 1$ **then**

7: $S \leftarrow 2Q$

8: $P \leftarrow f_P(P+Q) + R - S$

9: $Q \leftarrow S$

10: **else**

11: $S \leftarrow 2P$

12: $Q \leftarrow f_P(Q + P) + R - S$

13: $P \leftarrow S$

14: **end if**

15: **end for**

16: **return** $P$

**output** $P = kA$

In the case $\ell_P = 1$, Equation (2a) $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the fully-interleaved ladders is equivalent to:

$$ \begin{cases} 2g_P + g_Q = 2 \\ g_P + \frac{g_Q}{3 - 2f_P} + g_A = 1 + \frac{1}{3 - 2f_P} \end{cases} $$

So $g_Q = 2(1 - g_P)$ and $g_A = 1 + \frac{(2f_P - 1)g_P - 1}{3 - 2f_P}$. Thus Equation (2d) $g(f(\ell(x), x), x) = \varepsilon(x)$ for the fully-interleaved ladders implies that $\frac{2(f_P(g_P - 1) + 1)}{3 - 2f_P}A = \mathcal{O}$. To avoid constraint on $A$, we assume $f_P(g_P - 1) + 1 = 0$; i.e., $g_P = 1 - \frac{1}{f_P}$.

**Theorem 5.** The double-and-add algorithm with $\theta(P) = 2P + A$ and $\varepsilon(P) = 2P$ is fully-ladderizable with:

$$ f(P,Q) = f_P \left( P - Q - \frac{1}{3-2f_P} A \right) + 2Q + \frac{1}{3-2f_P} A $$

$$ g(P,Q) = P + \frac{1}{f_P} \left( -P + 2Q + \frac{1}{3-2f_P} A \right) - \frac{1}{3-2f_P} A $$

$$ \ell(P) = P + \frac{1}{3-2f_P} A $$

where $f_P \neq 0, 1, 2$, and where $f_P$ and $3 - 2f_P$ are invertible, producing (after memoization in R and S) Algorithm 16.

Note that, because the coefficients are chosen in $\mathbb{F}_p$ with $p$ prime, if $f_P \neq 0$ and $f_P \neq 3 \times 2^{-1}$, then $f_P$ and $3 - 2f_P$ are invertible. Hence, $f_P$ can be
<caption>**Algorithm 16** Fully-Interleaved Ladder for the Scalar Multiplication</caption>

**input** public $p, A$; secret $k$
1: $P \leftarrow \mathcal{O}$
2: $f_P \leftarrow \text{random}(\mathbb{F}_p \setminus \{0, 1, 2, 3 \times 2^{-1}\})$
3: $C \leftarrow \frac{1}{3-2f_P} A$
4: $c_0 \leftarrow \frac{1}{f_P}$
5: $Q \leftarrow C$
6: **for** $i = d$ **to** 0 **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R \leftarrow P - C$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 2Q + C$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow f_P(R - Q) + S$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q \leftarrow c_0(S - P) + R$
12: &nbsp;&nbsp;&nbsp;&nbsp;**else**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R \leftarrow Q - C$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 2P + C$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q \leftarrow f_P(R - P) + S$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow c_0(S - Q) + R$
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
19: **return** $P$
**output** $P = kA$

randomly generated (Line 2) while satisfying constraints from Theorem 5. As in Subsection 5.2, this provides a blinding integer reducing vulnerability to advanced side-channel attacks like CPA [10]. Because $C$ and $c_0$ depends only on $f_P$ and $A$, they can be precomputed before the loop (Lines 3 and 4). We discuss in Subsection 6.4 the feasibility and performance of the scalar multiplications by $f_P$ and $c_0$ involved in the algorithm.

## 6.4 Application to ECC

In this subsection, we discuss the feasibility of the novel algorithms obtained for the scalar multiplication in ECC. These algorithms are the first semi-interleaved ladder in Theorem 4 requiring a scalar multiplication by $f_P$, and the fully-interleaved ladder in Theorem 5 requiring a scalar multiplication by $\frac{1}{3-2f_P}$ during initialization, then $f_P$ and $\frac{1}{f_P}$ during each iteration. These scalar multiplications can be costly, so they are a challenge regarding performance (RQ3).

Scalar multiplications $cA$ for various scalar coefficients $c$ can be precomputed if $A$ is a fixed

point, as in the DSA signing step or the first step of Diffie-Hellman protocol. This is the case for the scalar multiplication by $\frac{1}{3-2f_P}$, but not for the other cases, which involve scalar multiplications for non-fixed points $R$, linear combination of $A, P$, and $Q$.

A scalar multiplication $cR$ for a specific coefficient $c$ can be efficiently computed, i.e., with very few field operations, by using an elliptic curve endowed with an efficient endomorphism. On such curves, there exists a constant $\lambda$, depending on the prime modulus $p$ and the parameters of the curve (Definition 1 p.6), such that $\lambda R$ can be computed with very few multiplications (only one in most cases) on $\mathbb{F}_p$. This is detailed in [16], where the authors describe the GLV (Gallant, Lambert, and Vanstone) method used in various standards, like the Bitcoin protocol specification or TLS (Transport Layer Security) [41].

Another way to optimize the cost of $cR$ is to use a short addition chain [29], so that the number of point operations required to compute $cR$ is equal to the length of the chain. The problem of computing the shortest addition chain for a given integer is hard [3], but for “small” integers there exists tables [8] providing the corresponding chain.

So, for the first semi-interleaved ladder in Theorem 4, one can use an elliptic curve endowed with an efficient endomorphism $\lambda$ and assign $f_P = \lambda$. Or, for a non-specific curve, one can choose $f_P$ amongst the integers corresponding to “very short” addition chains.

But these methods should not be used together. Indeed, when an efficient endomorphism is available for the chosen elliptic curve, multiplications on $\mathbb{F}_p$ are largely less costly than the additions and doublings required in addition chains, even very short ones. Hence, an attacker would be able to infer the method used to choose $f_P$, by leveraging even simple side-channel attacks [32, 31].

Moreover, there usually exists (if any) at most one or two (known) efficient endomorphism for a given elliptic curve [16]. Hence, because of the small range of values, efficient endomorphisms cannot be used as blinding integers.

Thus, to preserve $f_P$ as a blinding integer for the semi-interleaved ladder (Algorithm 15), it must be randomly chosen amongst values corresponding to very short addition chains. This largely reduces the range for the random blinding integer, but this
<caption>**Algorithm 16** Fully-Interleaved Ladder for the Scalar Multiplication</caption>

**input** public $p, A$; secret $k$
1: $P \leftarrow \mathcal{O}$
2: $f_P \leftarrow \text{random}(\mathbb{F}_p \setminus \{0, 1, 2, 3 \times 2^{-1}\})$
3: $C \leftarrow \frac{1}{3-2f_P} A$
4: $c_0 \leftarrow \frac{1}{f_P}$
5: $Q \leftarrow C$
6: **for** $i = d$ **to** 0 **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R \leftarrow P - C$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 2Q + C$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow f_P(R - Q) + S$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q \leftarrow c_0(S - P) + R$
12: &nbsp;&nbsp;&nbsp;&nbsp;**else**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R \leftarrow Q - C$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 2P + C$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q \leftarrow f_P(R - P) + S$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$P \leftarrow c_0(S - Q) + R$
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
19: **return** $P$
**output** $P = kA$

randomly generated (Line 2) while satisfying constraints from Theorem 5. As in Subsection 5.2, this provides a blinding integer reducting vulnerability to advanced side-channel attacks like CPA [10]. Because $C$ and $c_0$ depends only on $f_P$ and $A$, they can be precomputed before the loop (Lines 3 and 4). We discuss in Subsection 6.4 the feasibility and performance of the scalar multiplications by $f_P$ and $c_0$ involved in the algorithm.

## 6.4 Application to ECC

In this subsection, we discuss the feasability of the novel algorithms obtained for the scalar multiplication in ECC. These algorithms are the first semi-interleaved ladder in Theorem 4 requiring a scalar multiplication by $f_P$, and the fully-interleaved ladder in Theorem 5 requiring a scalar multiplication by $\frac{1}{3-2f_P}$ during initialization, then $f_P$ and $\frac{1}{f_P}$ during each iteration. These scalar multiplications can be costly, so they are a challenge regarding performance (RQ3).

Scalar multiplications $cA$ for various scalar coefficients $c$ can be precomputed if $A$ is a fixed

point, as in the DSA signing step or the first step of Diffie-Hellman protocol. This is the case for the scalar multiplication by $\frac{1}{3-2f_P}$, but not for the other cases, which involve scalar multiplications for non-fixed points $R$, linear combination of $A, P$, and $Q$.

A scalar multiplication $cR$ for a specific coefficient $c$ can be efficiently computed, i.e., with very few field operations, by using an elliptic curve endowed with an efficient endomorphism. On such curves, there exists a constant $\lambda$, depending on the prime modulus $p$ and the parameters of the curve (Definition 1 p.6), such that $\lambda R$ can be computed with very few multiplications (only one in most cases) on $\mathbb{F}_p$. This is detailed in [16], where the authors describe the GLV (Gallant, Lambert, and Vanstone) method used in various standards, like the Bitcoin protocol specification or TLS (Transport Layer Security) [41].

Another way to optimize the cost of $cR$ is to use a short addition chain [29], so that the number of point operations required to compute $cR$ is equal to the length of the chain. The problem of computing the shortest addition chain for a given integer is hard [3], but for “small” integers there exists tables [8] providing the corresponding chain.

So, for the first semi-interleaved ladder in Theorem 4, one can use an elliptic curve endowed with an efficient endomorphism $\lambda$ and assign $f_P = \lambda$. Or, for a non-specific curve, one can choose $f_P$ amongst the integers corresponding to “very short” addition chains.

But these methods should not be used together. Indeed, when an efficient endomorphism is available for the chosen elliptic curve, multiplications on $\mathbb{F}_p$ are largely less costly than the additions and doublings required in addition chains, even very short ones. Hence, an attacker would be able to infer the method used to choose $f_P$, by leveraging even simple side-channel attacks [32, 31].

Moreover, there usually exists (if any) at most one or two (known) efficient endomorphism for a given elliptic curve [16]. Hence, because of the small range of values, efficient endomorphisms cannot be used as blinding integers.

Thus, to preserve $f_P$ as a blinding integer for the semi-interleaved ladder (Algorithm 15), it must be randomly chosen amongst values corresponding to very short addition chains. This largely reduces the range for the random blinding integer, but this
makes this algorithm practical in the context of
ECC.

For the fully-interleaved ladder (Theorem 5), neither an efficient endomorphism nor an addition chain can be used. Indeed, that $f_P R$ can be efficiently computed does not imply that $\frac{1}{f_P} R$ can also be efficiently computed, because both coefficients are dependent. Therefore, Algorithm 16 is, to our knowledge, not feasible in practice in the context of ECC.

## 6.5 Complexity

We remind that we consider solutions involving non-secure scalar multiplications with public scalars in order to compute secure scalar multiplications with sensitive scalars. We provide in Table 4 a comparison of complexities for the Montgomery, semi- and fully-interleaved ladders. As in Subsection 5.4, we consider both sequential and parallel cases, and the complexities are given in terms of cost per key bit, where *M* stands for non-secure scalar multiplication, *D* for doubling, and *A* for addition/subtraction of points of the elliptic curve.

The line “without optimization” of Table 4 demonstrates a trade-off between security and performance. As opposed to the Montgomery ladder, the semi-interleaved solution from Theorem 4 has a blinding integer reducing the vulnerability of intermediate values against advanced side-channel attacks, but at the price of a non-secure scalar multiplication for each key bit. Moreover, as illustrated in Table 1 p.14, the fully-interleaved solution from Theorem 5 is better protected against fault-injection attacks, but this time at the price of two non-secure scalar multiplications for each key bit.

The cost of the semi-interleaved ladder solution is detailed at the third column of Table 4. Since the cost of a few multiplications on $F_p$ is negligible compared to point doubling or addition/subtraction, if an efficient endomorphism is available, this solution is almost as performant as the Montgomery ladder. But, as detailed in Subsection 6.4, such an efficient endomorphism cannot be used for the blinding integer. Hence, in this case, the Montgomery ladder dominates our semi-interleaved ladder solution. With short addition chains, the cost depends on the constant $f_P$ and is denoted $cost_{f_P}(D, A)$, consisting on (a small number of) doubling and addition/subtraction operations. This time, as detailed

in Subsection 6.4, a blinding integer can be used but at the price of several operations, demonstrating a trade-off between security and performance.

The cost of the fully-interleaved ladder solution is detailed at the last column of Table 4. Because of the dependency between $f_P$ and $\frac{1}{f_P}$, determining an efficient endomorphism or a short addition chain for both coefficients is an open problem.

Finally, as in Subsection 5.4, we also consider parallel computations (Subsection 2.5) to evaluate performance. The second part of Table 4 provides a comparison when the algorithms run on a multi-core system. We consider the then branch of our semi-interleaved ladder (Algorithm 15), both branches having the same complexity. First, the doubling $S \leftarrow 2Q$ is computed. Then, $f_P(P+Q)$ and $R-S$ can be independently computed in one scalar multiplication and one addition. Finally the results are added together and $Q$ receives the value from $S$.

In the same way, we consider the then branch of our fully-interleaved ladder (Algorithm 16). *R* and *S* can be independently computed in one doubling and one addition, gaining one addition, then *P* and *Q* are sequentially computed. In both cases, only one addition operation is gained, which does not change our conclusions from the sequential case.

## 6.6 Results for the Scalar Multiplication

In this section we provided concrete answers to **RQ1** by solving the ladder equations for the scalar multiplication in ECC. We obtained Algorithm 15 for the semi-interleaved case and Algorithm 16 for the fully-interleaved case.

Algorithm 15 uses a blinding integer, providing more protection against power side-channel attacks than the Montgomery ladder, for instance against advanced power attacks like CPA [10]. As in Subsection 5.7, this protection naturally arose from a free parameter while solving the ladder equations, thus demonstrating again the fruitfulness of the ladderization approach (**RQ2**). Moreover, as detailed in Subsection 4.3, Algorithm 16 is more secure against fault-injection attacks than the Montgomery ladder. So, the security properties of the Montgomery ladder have not only been generalized but improved in both cases.
makes this algorithm practical in the context of
ECC.

For the fully-interleaved ladder (Theorem 5), neither an efficient endomorphism nor an addition chain can be used. Indeed, that $f_{PR}$ can be efficiently computed does not imply that $\frac{1}{f_P}R$ can also be efficiently computed, because both coefficients are dependent. Therefore, Algorithm 16 is, to our knowledge, not feasible in practice in the context of ECC.

## 6.5 Complexity

We remind that we consider solutions involving non-secure scalar multiplications with public scalars in order to compute secure scalar multiplications with sensitive scalars. We provide in Table 4 a comparison of complexities for the Montgomery, semi- and fully-interleaved ladders. As in Subsection 5.4, we consider both sequential and parallel cases, and the complexities are given in terms of cost per key bit, where *M* stands for non-secure scalar multiplication, *D* for doubling, and *A* for addition/subtraction of points of the elliptic curve.

The line “without optimization” of Table 4 demonstrates a trade-off between security and performance. As opposed to the Montgomery ladder, the semi-interleaved solution from Theorem 4 has a blinding integer reducing the vulnerability of intermediate values against advanced side-channel attacks, but at the price of a non-secure scalar multiplication for each key bit. Moreover, as illustrated in Table 1 p.14, the fully-interleaved solution from Theorem 5 is better protected against fault-injection attacks, but this time at the price of two non-secure scalar multiplications for each key bit.

The cost of the semi-interleaved ladder solution is detailed at the third column of Table 4. Since the cost of a few multiplications on $F_p$ is negligible compared to point doubling or addition/subtraction, if an efficient endomorphism is available, this solution is almost as performant as the Montgomery ladder. But, as detailed in Subsection 6.4, such an efficient endomorphism cannot be used for the blinding integer. Hence, in this case, the Montgomery ladder dominates our semi-interleaved ladder solution. With short addition chains, the cost depends on the constant $f_P$ and is denoted $cost_{f_P}(D, A)$, consisting on (a small number of) doubling and addition/subtraction operations. This time, as detailed

in Subsection 6.4, a blinding integer can be used but at the price of several operations, demonstrating a trade-off between security and performance.

The cost of the fully-interleaved ladder solution is detailed at the last column of Table 4. Because of the dependency between $f_P$ and $\frac{1}{f_P}$, determining an efficient endomorphism or a short addition chain for both coefficients is an open problem.

Finally, as in Subsection 5.4, we also consider parallel computations (Subsection 2.5) to evaluate performance. The second part of Table 4 provides a comparison when the algorithms run on a multi-core system. We consider the then branch of our semi-interleaved ladder (Algorithm 15), both branches having the same complexity. First, the doubling $S \leftarrow 2Q$ is computed. Then, $f_P(P+Q)$ and $R-S$ can be independently computed in one scalar multiplication and one addition. Finally the results are added together and $Q$ receives the value from $S$.

In the same way, we consider the then branch of our fully-interleaved ladder (Algorithm 16). *R* and *S* can be independently computed in one doubling and one addition, gaining one addition, then *P* and *Q* are sequentially computed. In both cases, only one addition operation is gained, which does not change our conclusions from the sequential case.

## 6.6 Results for the Scalar Multiplication

In this section we provided concrete answers to **RQ1** by solving the ladder equations for the scalar multiplication in ECC. We obtained Algorithm 15 for the semi-interleaved case and Algorithm 16 for the fully-interleaved case.

Algorithm 15 uses a blinding integer, providing more protection against power side-channel attacks than the Montgomery ladder, for instance against advanced power attacks like CPA [10]. As in Subsection 5.7, this protection naturally arose from a free parameter while solving the ladder equations, thus demonstrating again the fruitfulness of the ladderization approach (**RQ2**). Moreover, as detailed in Subsection 4.3, Algorithm 16 is more secure against fault-injection attacks than the Montgomery ladder. So, the security properties of the Montgomery ladder have not only been generalized but improved in both cases.
<table><caption>Table 4: Cost per bit (after memoization) of the Montgomery (Algorithm 5 p.7), semi- (Algorithm 15) and fully-interleaved ladders (Algorithm 16) for the secure scalar multiplication, where *M* stands for non-secure scalar multiplication, *A* for addition or subtraction, and *D* for doubling</caption><thead><tr><th></th><th>Montgomery</th><th>Semi-Interleaved</th><th>Fully-Interleaved</th></tr></thead><tbody><tr><td>sequential</td><td></td><td></td><td></td></tr><tr><td>without optimization</td><td>A + D</td><td>M + 3A + D</td><td>2M + 6A + D</td></tr><tr><td>efficient endomorphism</td><td>A + D</td><td>3A + D</td><td>open problem</td></tr><tr><td>addition chain</td><td>A + D</td><td>cost<sub>f<sub>P</sub></sub>(D, A) + 3A + D</td><td>open problem</td></tr><tr><td>parallel</td><td></td><td></td><td></td></tr><tr><td>without optimization</td><td>A + D</td><td>M + 2A + D</td><td>2M + 5A + D</td></tr><tr><td>efficient endomorphism</td><td>A + D</td><td>2A + D</td><td>open problem</td></tr><tr><td>addition chain</td><td>A + D</td><td>cost<sub>f<sub>P</sub></sub>(D, A) + 2A + D</td><td>open problem</td></tr></tbody></table>

We also compared the complexity of these novel algorithms in Subsection 6.5 with the complexity of the Montgomery ladder in ECC (Algorithm 5 p.7). The trade-off between security and performance is less favorable than in Subsection 5.4, because we use scalar multiplications on public values to compute scalar multiplications on the secret key.

These scalar multiplications raise a challenge regarding performance (RQ3), that we tackled in two ways. First, by leveraging (if any) an efficient endomorphism to compute these scalar multiplications. In that case, a blinding integer cannot be used and performance is no better than the common Montgomery ladder, which thus dominates our solution. Second, by restricting the blinding integer in Algorithm 15 to integers computed using short addition chains. This makes Algorithm 15 feasible, but at the price of limiting the range of values for the blinding integer and thus the protection against advanced power attacks. Finally, efficient endomorphisms or addition chains were not applicable to Algorithm 16 which is thus, to our knowledge, not feasible in practice in the context of ECC.

# 7 Conclusion

A ladderization is a process refactoring a sensitive iterative conditional branching into a semi- or fully-interleaved ladder, in order to protect sensitive information from various side-channel or fault-injection attacks. These interleaved ladders are obtained through solving ladder equations for the system of interest. We evaluated the ladderization approach with three research questions:

* RQ1: To which extent can the algorithmic strength of the Montgomery ladder be generalized to other algorithms?

* RQ2: How secure are interleaved ladders compared to the Montgomery ladder?

* RQ3: How feasible are interleaved ladders in practice and, if so, how performant are they compared to the Montgomery ladder?

## 7.1 Answers to the Research Questions

Theorem 1 provided a theoretical answer to RQ1, by characterizing the ladderizable algorithms. To provide a more concrete answer, we solved the ladder equations in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication. Security properties from the Montgomery ladder are preserved. First, the obtained code symmetry allows a protection against simple side-channel attacks like timing attacks [32] or SPA [31]. Second, a violation of the invariant $y = l(x)$ allows the algorithm to detect a fault-injection attack, potentially triggering a self-secure countermeasure.

RQ2 is answered in two ways. Exhaustively investigating fault-propagation patterns lead to the discovery of three novel fault-injection attacks described in Section 4. Moreover, interleaved ladders can be even more secure than the Montgomery ladder. First, as described in Table 1, fully-interleaved ladders are more secure than the Montgomery ladder against fault-injection attacks. Second, ladder equations in Subsections 5.2, 5.3 and 6.2 allows for all solutions except the fully-interleaved ladder
<table><caption>Table 4: Cost per bit (after memoization) of the Montgomery (Algorithm 5 p.7), semi- (Algorithm 15) and fully-interleaved ladders (Algorithm 16) for the secure scalar multiplication, where *M* stands for non-secure scalar multiplication, *A* for addition or subtraction, and *D* for doubling</caption><thead><tr><th></th><th>Montgomery</th><th>Semi-Interleaved</th><th>Fully-Interleaved</th></tr></thead><tbody><tr><td>sequential</td><td></td><td></td><td></td></tr><tr><td>without optimization</td><td>A + D</td><td>M + 3A + D</td><td>2M + 6A + D</td></tr><tr><td>efficient endomorphism</td><td>A + D</td><td>3A + D</td><td>open problem</td></tr><tr><td>addition chain</td><td>A + D</td><td>cost<sub>f<sub>P</sub></sub>(D, A) + 3A + D</td><td>open problem</td></tr><tr><td>parallel</td><td></td><td></td><td></td></tr><tr><td>without optimization</td><td>A + D</td><td>M + 2A + D</td><td>2M + 5A + D</td></tr><tr><td>efficient endomorphism</td><td>A + D</td><td>2A + D</td><td>open problem</td></tr><tr><td>addition chain</td><td>A + D</td><td>cost<sub>f<sub>P</sub></sub>(D, A) + 2A + D</td><td>open problem</td></tr></tbody></table>

We also compared the complexity of these novel algorithms in Subsection 6.5 with the complexity of the Montgomery ladder in ECC (Algorithm 5 p.7). The trade-off between security and performance is less favorable than in Subsection 5.4, because we use scalar multiplications on public values to compute scalar multiplications on the secret key.

These scalar multiplications raise a challenge regarding performance (RQ3), that we tackled in two ways. First, by leveraging (if any) an efficient endomorphism to compute these scalar multiplications. In that case, a blinding integer cannot be used and performance is no better than the common Montgomery ladder, which thus dominates our solution. Second, by restricting the blinding integer in Algorithm 15 to integers computed using short addition chains. This makes Algorithm 15 feasible, but at the price of limiting the range of values for the blinding integer and thus the protection against advanced power attacks. Finally, efficient endomorphisms or addition chains were not applicable to Algorithm 16 which is thus, to our knowledge, not feasible in practice in the context of ECC.

# 7 Conclusion

A ladderization is a process refactoring a sensitive iterative conditional branching into a semi- or fully-interleaved ladder, in order to protect sensitive information from various side-channel or fault-injection attacks. These interleaved ladders are obtained through solving ladder equations for the system of interest. We evaluated the ladderization approach with three research questions:

* RQ1: To which extent can the algorithmic strength of the Montgomery ladder be generalized to other algorithms?

* RQ2: How secure are interleaved ladders compared to the Montgomery ladder?

* RQ3: How feasible are interleaved ladders in practice and, if so, how performant are they compared to the Montgomery ladder?

## 7.1 Answers to the Research Questions

Theorem 1 provided a theoretical answer to RQ1, by characterizing the ladderizable algorithms. To provide a more concrete answer, we solved the ladder equations in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication. Security properties from the Montgomery ladder are preserved. First, the obtained code symmetry allows a protection against simple side-channel attacks like timing attacks [32] or SPA [31]. Second, a violation of the invariant $y = l(x)$ allows the algorithm to detect a fault-injection attack, potentially triggering a self-secure countermeasure.

RQ2 is answered in two ways. Exhaustively investigating fault-propagation patterns lead to the discovery of three novel fault-injection attacks described in Section 4. Moreover, interleaved ladders can be even more secure than the Montgomery ladder. First, as described in Table 1, fully-interleaved ladders are more secure than the Montgomery ladder against fault-injection attacks. Second, ladder equations in Subsections 5.2, 5.3 and 6.2 allows for all solutions except the fully-interleaved ladder
for scalar multiplication the use of blinding inte-
gers, which provide protection against more com-
plex side-channel attacks like CPA [10].

But this increased protection came at the price
of performance, which raised several challenges re-
garding feasibility (RQ3).

In the case of modular exponentiation, our semi-
interleaved solution is 3 (resp. 2) times more
costly using sequential (resp. parallel) operations,
and our fully-interleaved solution is 5 (resp. 3)
more costly than the Montgomery ladder. But
we also demonstrated that, in practice, our semi-
interleaved solution is only 1.4 times more costly
than the Montgomery ladder, indicating that for
several cores and large key sizes their performances
are similar. Moreover, our fully-interleaved solu-
tion requires a ladder constant, which could be
costly to obtain in general. Fortunately, we proved
in the case of the RSA [45] (Subsection 5.5) and
DSA [40] (Subsection 5.6) cryptosystems that this
ladder constant can be obtained at a small cost with
probability almost equal to 1.

In the case of scalar multiplication, one or two
non-secure scalar multiplication(s) per secret bit
are required to compute one secure scalar multi-
plication, which is tremendously costly. To tackle
this challenge in the context of ECC, we investi-
gated efficient endomorphisms. Unfortunately, this
solution was not as performant as the Montgomery
ladder, while providing the same security proper-
ties, hence has to be rejected. We investigated an-
other solution, that restricts the blinding integer
in Algorithm 15 to integers computed using short
addition chains. We proved that in this case the
semi-interleaved ladder is feasible in practice, but
at the price of limiting the range of values for the
blinding integer and thus the protection against ad-
vanced power attacks. But such a solution was not
applicable to the fully-interleaved ladder, which is
thus, to our knowledge, not feasible in practice in
the context of ECC.

7.2 Future Work

The feasibility of the fully-interleaved ladder in the
context of ECC depends on the efficient computa-
tion of several dependent coefficients for the scalar
multiplications, which is an open and interesting
problem.

Moreover, our approach has been already auto-
mated [11] for the semi-interleaved ladders in the
**if-then** case, which remains to be done in the gen-
eral case for both semi- and fully-interleaved lad-
ders.

Finally, we only investigated the uni-
variate case for conditional branching, but
the multivariate case may be of interest.
For instance, a multi-variable polynomial
$\sum_{0 \le n \le d} \sum_{n_1 + \dots + n_k = n} c_{n_1, \dots, n_k} \prod_{1 \le i \le k} x_i^{n_i}$ can
be represented by a multidimensional array of
coefficients, thus the manipulation of ladder equa-
tions could be handled using matrix operations.

Acknowledgments

This work was supported by the
EU Horizon 2020 project TeamPlay
(https://www.teamplay-h2020.eu), grant
number 779882.

References

[1] Samuel Antão, Jean-Claude Bajard, and Leonel Sousa. Rns-based elliptic curve point multiplication for massive parallel architectures. *The Computer Journal*, 55(5):629-647, 2012.

[2] Jean Arlat. *Validation de la sûreté de fonctionnement par injection de fautes : méthode, mise en oeuvre, application*. PhD thesis, Institut national polytechnique (Toulouse, France), 1990.

[3] Hatem M. Bahig. Improved generation of minimal addition chains. *Computing*, 78(2):161-172, 2006.

[4] Elaine B. Barker, Lidong Chen, Allen L. Roginsky, Richard Davis, and Scott Simon. *Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography*. Number 800-56B Rev. 2 in Special Publication. NIST SP, March 2019.

[5] Elaine B. Barker, LiLy Chen, Allen L. Roginsky, Apostol Vassilev, and Richard Davis.
for scalar multiplication the use of blinding inte-
gers, which provide protection against more com-
plex side-channel attacks like CPA [10].

But this increased protection came at the price
of performance, which raised several challenges re-
garding feasibility (RQ3).

In the case of modular exponentiation, our semi-
interleaved solution is 3 (resp. 2) times more
costly using sequential (resp. parallel) operations,
and our fully-interleaved solution is 5 (resp. 3)
more costly than the Montgomery ladder. But
we also demonstrated that, in practice, our semi-
interleaved solution is only 1.4 times more costly
than the Montgomery ladder, indicating that for
several cores and large key sizes their performances
are similar. Moreover, our fully-interleaved solu-
tion requires a ladder constant, which could be
costly to obtain in general. Fortunately, we proved
in the case of the RSA [45] (Subsection 5.5) and
DSA [40] (Subsection 5.6) cryptosystems that this
ladder constant can be obtained at a small cost with
probability almost equal to 1.

In the case of scalar multiplication, one or two
non-secure scalar multiplication(s) per secret bit
are required to compute one secure scalar multi-
plication, which is tremendously costly. To tackle
this challenge in the context of ECC, we investi-
gated efficient endomorphisms. Unfortunately, this
solution was not as performant as the Montgomery
ladder, while providing the same security proper-
ties, hence has to be rejected. We investigated an-
other solution, that restricts the blinding integer
in Algorithm 15 to integers computed using short
addition chains. We proved that in this case the
semi-interleaved ladder is feasible in practice, but
at the price of limiting the range of values for the
blinding integer and thus the protection against ad-
vanced power attacks. But such a solution was not
applicable to the fully-interleaved ladder, which is
thus, to our knowledge, not feasible in practice in
the context of ECC.

7.2 Future Work

The feasibility of the fully-interleaved ladder in the
context of ECC depends on the efficient computa-
tion of several dependent coefficients for the scalar
multiplications, which is an open and interesting
problem.

Moreover, our approach has been already auto-
mated [11] for the semi-interleaved ladders in the
**if-then** case, which remains to be done in the gen-
eral case for both semi- and fully-interleaved lad-
ders.

Finally, we only investigated the uni-
variate case for conditional branching, but
the multivariate case may be of interest.
For instance, a multi-variable polynomial
$\sum_{0 \le n \le d} \sum_{n_1 + \dots + n_k = n} c_{n_1, \dots, n_k} \prod_{1 \le i \le k} x_i^{n_i}$ can
be represented by a multidimensional array of
coefficients, thus the manipulation of ladder equa-
tions could be handled using matrix operations.

Acknowledgments

This work was supported by the
EU Horizon 2020 project TeamPlay
(https://www.teamplay-h2020.eu), grant
number 779882.

References

[1] Samuel Antão, Jean-Claude Bajard, and Leonel Sousa. Rns-based elliptic curve point multiplication for massive parallel architectures. *The Computer Journal*, 55(5):629-647, 2012.

[2] Jean Arlat. *Validation de la sûreté de fonctionnement par injection de fautes : méthode, mise en oeuvre, application*. PhD thesis, Institut national polytechnique (Toulouse, France), 1990.

[3] Hatem M. Bahig. Improved generation of minimal addition chains. *Computing*, 78(2):161-172, 2006.

[4] Elaine B. Barker, Lidong Chen, Allen L. Roginsky, Richard Davis, and Scott Simon. *Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography*. Number 800-56B Rev. 2 in Special Publication. NIST SP, March 2019.

[5] Elaine B. Barker, LiLy Chen, Allen L. Roginsky, Apostol Vassilev, and Richard Davis.
*Recommendation for Pair-Wise Key Establishment Using Dicrete Logarithm Cryptography*. Number 800-56A Rev. 3 in Special Publication. NIST SP, , April 2018.

[6] Saikat Basu. A new parallel window-based implementation of the elliptic curve point multiplication in multi-core architectures. *Group*, 16(4a3):27b2, 2012.

[7] Daniel J Bernstein, Hsueh-Chung Chen, Ming-Shing Chen, Chen-Mou Cheng, Chun-Hung Hsiao, Tanja Lange, Zong-Cing Lin, and Bo-Yin Yang. The billion-mulmod-per-second pc. In *Workshop record of SHARCS*, volume 9, pages 131–144, 2009.

[8] Olivier Billet. Addition chains (accessed may 9, 2023).

[9] Arnaud Boscher, Robert Naciri, and Emmanuel Prouff. CRT RSA Algorithm Protected Against Fault Attacks. In Damien Sauveron, Konstantinos Markantonakis, Angelos Bilas, and Jean-Jacques Quisquater, editors, *Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems*, pages 229–243, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[10] Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In *International workshop on cryptographic hardware and embedded systems*, pages 16–29. Springer, 2004.

[11] Christopher Brown, Adam D. Barwell, Yoann Marquer, Olivier Zendra, Tania Richmond, and Chen Gu. Semi-automatic ladderisation: Improving code security through rewriting and dependent types. In *Proceedings of the 2022 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation*, PEPM 2022, page 14–27, New York, NY, USA, 2022. Association for Computing Machinery.

[12] Christophe Clavier, Benoit Feix, Georges Gagnerot, Mylène Roussellet, and Vincent Verneuil. Square Always Exponentiation. In Daniel J. Bernstein and Sanjit Chatterjee, editors, *Progress in Cryptology – INDOCRYPT 2011*, pages 40–57, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[13] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, editors. *Handbook of Elliptic and Hyperelliptic Curve Cryptography*. Chapman and Hall/CRC, , 2005.

[14] Jean-Sébastien Coron. Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems. In Çetin K. Koç and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems*, pages 292–302, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[15] Junfeng Fan, Kazuo Sakiyama, and Ingrid Verbauwhede. Elliptic curve cryptography on embedded multicore systems. *Design Automation for Embedded Systems*, 12:231–242, 2008.

[16] Robert P. Gallant, Robert J. Lambert, and Scott Alexander Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In *Advances in Cryptology — CRYPTO*, volume 2139 of LNCS, pages 190–200, , 2001. Springer.

[17] Carl Friedrich Gauss and Arthur A. Clarke. *Disquisitiones Arithmeticae*. Yale University Press, , 1965.

[18] C. Giraud. An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis. *IEEE Transactions on Computers*, 55(9):1116–1120, Sep. 2006.

[19] GMP. Gnu multiple precision arithmetic library (gmp) (accessed august 6, 2023).

[20] JaeCheol Ha, YongJe Choi, Dooho Choi, and Hoonjae Lee. Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm. *J. Internet Serv. Inf. Secur.*, 4:38–51, 2014.

[21] Neil Hanley, HeeSeok Kim, and Michael Tunt stall. Exploiting Collisions in Addition Chain- Based Exponentiation Algorithms Using a Single Trace. In Kaisa Nyberg, editor, *Topics in Cryptology — CT-RSA 2015*, pages 431–448, Cham, 2015. Springer International Publishing.

[22] Marc Joye. Highly Regular Right-to-Left Algorithms for Scalar Multiplication. In Pascal Paillier and Ingrid Verbauwhede, editors,
*Recommendation for Pair-Wise Key Establishment Using Dicrete Logarithm Cryptography*. Number 800-56A Rev. 3 in Special Publication. NIST SP, , April 2018.

[6] Saikat Basu. A new parallel window-based implementation of the elliptic curve point multiplication in multi-core architectures. *Group*, 16(4a3):27b2, 2012.

[7] Daniel J Bernstein, Hsueh-Chung Chen, Ming-Shing Chen, Chen-Mou Cheng, Chun-Hung Hsiao, Tanja Lange, Zong-Cing Lin, and Bo-Yin Yang. The billion-mulmod-per-second pc. In *Workshop record of SHARCS*, volume 9, pages 131–144, 2009.

[8] Olivier Billet. Addition chains (accessed may 9, 2023).

[9] Arnaud Boscher, Robert Naciri, and Emmanuel Prouff. CRT RSA Algorithm Protected Against Fault Attacks. In Damien Sauveron, Konstantinos Markantonakis, Angelos Bilas, and Jean-Jacques Quisquater, editors, *Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems*, pages 229–243, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[10] Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In *International workshop on cryptographic hardware and embedded systems*, pages 16–29. Springer, 2004.

[11] Christopher Brown, Adam D. Barwell, Yoann Marquer, Olivier Zendra, Tania Richmond, and Chen Gu. Semi-automatic ladderisation: Improving code security through rewriting and dependent types. In *Proceedings of the 2022 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation*, PEPM 2022, page 14–27, New York, NY, USA, 2022. Association for Computing Machinery.

[12] Christophe Clavier, Benoit Feix, Georges Gagnerot, Mylène Roussellet, and Vincent Verneuil. Square Always Exponentiation. In Daniel J. Bernstein and Sanjit Chatterjee, editors, *Progress in Cryptology – INDOCRYPT 2011*, pages 40–57, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[13] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, editors. *Handbook of Elliptic and Hyperelliptic Curve Cryptography*. Chapman and Hall/CRC, , 2005.

[14] Jean-Sébastien Coron. Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems. In Çetin K. Koç and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems*, pages 292–302, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[15] Junfeng Fan, Kazuo Sakiyama, and Ingrid Verbauwhede. Elliptic curve cryptography on embedded multicore systems. *Design Automation for Embedded Systems*, 12:231–242, 2008.

[16] Robert P. Gallant, Robert J. Lambert, and Scott Alexander Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In *Advances in Cryptology — CRYPTO*, volume 2139 of LNCS, pages 190–200, , 2001. Springer.

[17] Carl Friedrich Gauss and Arthur A. Clarke. *Disquisitiones Arithmeticae*. Yale University Press, , 1965.

[18] C. Giraud. An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis. *IEEE Transactions on Computers*, 55(9):1116–1120, Sep. 2006.

[19] GMP. Gnu multiple precision arithmetic library (gmp) (accessed august 6, 2023).

[20] JaeCheol Ha, YongJe Choi, Dooho Choi, and Hoonjae Lee. Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm. *J. Internet Serv. Inf. Secur.*, 4:38–51, 2014.

[21] Neil Hanley, HeeSeok Kim, and Michael Tunt stall. Exploiting Collisions in Addition Chain- Based Exponentiation Algorithms Using a Single Trace. In Kaisa Nyberg, editor, *Topics in Cryptology — CT-RSA 2015*, pages 431–448, Cham, 2015. Springer International Publishing.

[22] Marc Joye. Highly Regular Right-to-Left Algorithms for Scalar Multiplication. In Pascal Paillier and Ingrid Verbauwhede, editors,
*Cryptographic Hardware and Embedded Systems* - CHES 2007, pages 135–147, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[23] Marc Joye. Highly Regular m-Ary Powering Ladders. In Michael J. Jacobson, Vincent Rijmen, and Reihaneh Safavi-Naini, editors, *Selected Areas in Cryptography*, pages 350–363, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.

[24] Marc Joye and Sung-Ming Yen. The Montgomery Powering Ladder. In Burton S. Kaliski, Çetin K. Koç, and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems - CHES 2002*, pages 291–302, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.

[25] Uma S. Kanniah and Azman Samsudin. Multithreading elliptic curve cryptosystems. In *2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications*, pages 134–139, May 2007.

[26] Auguste Kerckhoffs. La cryptographie militaire (military cryptography). *Sciences Militaires* (*J. Military Science, in French*), 9:5 – 38, January 1883.

[27] HeeSeok Kim, Tae Hyun Kim, Joong Chul Yoon, and Seokhie Hong. Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA. *ETRI Journal*, 32(1):102–111, 2010.

[28] Ágnes Kiss, Juliane Krämer, Pablo Rauzy, and Jean-Pierre Seifert. Algorithmic Countermeasures Against Fault Attacks and Power Analysis for RSA-CRT. In François-Xavier Standaert and Elisabeth Oswald, editors, *Constructive Side-Channel Analysis and Secure Design*, pages 111–129, Cham, 2016. Springer International Publishing.

[29] Donald Ervin Knuth. *The Art of Computer Programming: Fundamental Algorithms*, volume 2. Addison Wesley, 3rd edition, 07 1997.

[30] N. Koblitz. Elliptic Curve Cryptosystems. *Math. Comp*, 48:243–264, 01 1987.

[31] Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In Michael Wiener, editor, *Advances in Cryptology — CRYPTO' 99*, pages 388–397, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[32] Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Neal Koblitz, editor, *Advances in Cryptology — CRYPTO '96*, pages 104–113, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.

[33] Peter L. Montgomery. Montgomery, P.L.: Speeding the Pollard and Elliptic Curve Methods of Factorization. Math. Comp. 48, 243–264. *Mathematics of Computation* - Math. Comput., 48:243–243, 01 1987.

[34] Ladder benchmarks (accessed august 6, 2023).

[35] Duc-Phong Le, Chik How Tan, and Michael Tunstall. Randomizing the Montgomery Powering Ladder. In Raja Naeem Akram and Sushil Jajodia, editors, *Information Security Theory and Practice*, pages 169–184, Cham, 2015. Springer International Publishing.

[36] Yoann Marquer. Algorithmic Completeness of Imperative Programming Languages. *Fundamenta Informaticae*, 168(1):51–77, July 2019.

[37] Yoann Marquer and Tania Richmond. A hole in the ladder: Interleaved variables in iterative conditional branching. In *ARITH 2020 - 27th IEEE Symposium on Computer Arithmetic*, pages 56–63, Portland, Oregon, USA, United States, June 2020. IEEE.

[38] Thomas S. Messerges, Ezzy A. Dabbish, and Robert H. Sloan. Power Analysis Attacks of Modular Exponentiation in Smartcards. In Çetin K. Koç and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems*, pages 144–157, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[39] Victor S. Miller. Use of Elliptic Curves in Cryptography. In Hugh C. Williams, editor, *Advances in Cryptology — CRYPTO '85 Proceedings*, pages 417–426, Berlin, Heidelberg, 1986. Springer Berlin Heidelberg.
*Cryptographic Hardware and Embedded Systems* - CHES 2007, pages 135–147, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[23] Marc Joye. Highly Regular m-Ary Powering Ladders. In Michael J. Jacobson, Vincent Rijmen, and Reihaneh Safavi-Naini, editors, *Selected Areas in Cryptography*, pages 350–363, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.

[24] Marc Joye and Sung-Ming Yen. The Montgomery Powering Ladder. In Burton S. Kaliski, Çetin K. Koç, and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems - CHES 2002*, pages 291–302, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.

[25] Uma S. Kanniah and Azman Samsudin. Multithreading elliptic curve cryptosystems. In *2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications*, pages 134–139, May 2007.

[26] Auguste Kerckhoffs. La cryptographie militaire (military cryptography). *Sciences Miliataires* (*J. Military Science, in French*), 9:5 – 38, January 1883.

[27] HeeSeok Kim, Tae Hyun Kim, Joong Chul Yoon, and Seokhie Hong. Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA. *ETRI Journal*, 32(1):102–111, 2010.

[28] Ágnes Kiss, Juliane Krämer, Pablo Rauzy, and Jean-Pierre Seifert. Algorithmic Countermeasures Against Fault Attacks and Power Analysis for RSA-CRT. In François-Xavier Standaert and Elisabeth Oswald, editors, *Constructive Side-Channel Analysis and Secure Design*, pages 111–129, Cham, 2016. Springer International Publishing.

[29] Donald Ervin Knuth. *The Art of Computer Programming: Fundamental Algorithms*, volume 2. Addison Wesley, 3rd edition, 07 1997.

[30] N. Koblitz. Elliptic Curve Cryptosystems. *Math. Comp*, 48:243–264, 01 1987.

[31] Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In Michael Wiener, editor, *Advances in Cryptology — CRYPTO' 99*, pages 388–397, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[32] Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Neal Koblitz, editor, *Advances in Cryptology — CRYPTO '96*, pages 104–113, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.

[33] Peter L. Montgomery. Montgomery, P.L.: Speeding the Pollard and Elliptic Curve Methods of Factorization. Math. Comp. 48, 243–264. *Mathematics of Computation* - Math. Comput., 48:243–243, 01 1987.

[34] Ladder benchmarks (accessed august 6, 2023).

[35] Duc-Phong Le, Chik How Tan, and Michael Tunstall. Randomizing the Montgomery Powering Ladder. In Raja Naeem Akram and Sushil Jajodia, editors, *Information Security Theory and Practice*, pages 169–184, Cham, 2015. Springer International Publishing.

[36] Yoann Marquer. Algorithmic Completeness of Imperative Programming Languages. *Fundamenta Informaticae*, 168(1):51–77, July 2019.

[37] Yoann Marquer and Tania Richmond. A hole in the ladder: Interleaved variables in iterative conditional branching. In *ARITH 2020 - 27th IEEE Symposium on Computer Arithmetic*, pages 56–63, Portland, Oregon, USA, United States, June 2020. IEEE.

[38] Thomas S. Messerges, Ezzy A. Dabbish, and Robert H. Sloan. Power Analysis Attacks of Modular Exponentiation in Smartcards. In Çetin K. Koç and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems*, pages 144–157, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

[39] Victor S. Miller. Use of Elliptic Curves in Cryptography. In Hugh C. Williams, editor, *Advances in Cryptology — CRYPTO '85 Proceedings*, pages 417–426, Berlin, Heidelberg, 1986. Springer Berlin Heidelberg.
[40] National Institute of Standards and Technology. Digital signature standard (DSS). Technical Report Federal Information Processing Standards Publications (FIPS PUB) 186-4, U.S. Department of Commerce, Washington, D.C., July 2013.

[41] Yoav Nir, Simon Josefsson, and Manuel Pégourié-Gonnard. RFC8422: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS) versions 1.2 and earlier, 2020.

[42] Openmp api (accessed august 6, 2023).

[43] M. Petrvalsky, T. Richmond, M. Drutarovsky, P. Cayrel, and V. Fischer. Differential power analysis attack on the secure bit permutation in the McEliece cryptosystem. In *2016 26th International Conference Radioelektronika (RA-DIOELEKTRONIKA)*, pages 132–137, April 2016.

[44] E. Rescorla. RFC2631: Diffie-Hellman key agreement method, 1999.

[45] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. *Communications of the ACM*, 21(2):120–126, 1978.

[46] EFD Web site. Explicit formulas database.

[47] Falko Strenzke, Erik Tews, H. Gregor Molter, Raphael Overbeck, and Abdulhadi Shoufan. Side Channels in the McEliece PKC. In Johannes Buchmann and Jintai Ding, editors, *Post-Quantum Cryptography*, pages 216–229, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.

[48] Yen Sung-Ming, Seungjoo Kim, Seongan Lim, and Sangjae Moon. A Countermeasure against One Physical Cryptanalysis May Benefit Another Attack. In Kwangjo Kim, editor, *Information Security and Cryptology — ICISC 2001*, pages 414–427, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

[49] C. D. Walter. The Montgomery and Joye Powering Ladders are Dual. *IACR ePrint Archive*, 1081:1–6, 2017.

[50] H. Ziade, R. Ayoubi, and R. Velazco. A survey on fault injection techniques. *International Arab Journal of Information Technology*, Vol. 1, No. 2, July:171–186, 2004.
[40] National Institute of Standards and Technology. Digital signature standard (DSS). Technical Report Federal Information Processing Standards Publications (FIPS PUB) 186-4, U.S. Department of Commerce, Washington, D.C., July 2013.

[41] Yoav Nir, Simon Josefsson, and Manuel Pégourié-Gonnard. RFC8422: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS) versions 1.2 and earlier, 2020.

[42] Openmp api (accessed august 6, 2023).

[43] M. Petrvalsky, T. Richmond, M. Drutarovsky, P. Cayrel, and V. Fischer. Differential power analysis attack on the secure bit permutation in the McEliece cryptosystem. In *2016 26th International Conference Radioelektronika (RA-DIOELEKTRONIKA)*, pages 132–137, April 2016.

[44] E. Rescorla. RFC2631: Diffie-Hellman key agreement method, 1999.

[45] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. *Communications of the ACM*, 21(2):120–126, 1978.

[46] EFD Web site. Explicit formulas database.

[47] Falko Strenzke, Erik Tews, H. Gregor Molter, Raphael Overbeck, and Abdulhadi Shoufan. Side Channels in the McEliece PKC. In Johannes Buchmann and Jintai Ding, editors, *Post-Quantum Cryptography*, pages 216–229, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.

[48] Yen Sung-Ming, Seungjoo Kim, Seongan Lim, and Sangjae Moon. A Countermeasure against One Physical Cryptanalysis May Benefit Another Attack. In Kwangjo Kim, editor, *Information Security and Cryptology — ICISC 2001*, pages 414–427, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

[49] C. D. Walter. The Montgomery and Joye Powering Ladders are Dual. *IACR ePrint Archive*, 1081:1–6, 2017.

[50] H. Ziade, R. Ayoubi, and R. Velazco. A survey on fault injection techniques. *International Arab Journal of Information Technology*, Vol. 1, No. 2, July:171–186, 2004.