Contents

1. Basic Concepts

The Miller Loop is a fundamental algorithm in Elliptic Curve Cryptography (ECC) used for efficiently computing bilinear pairings, such as Weil and Tate pairings. These pairings are crucial in various cryptographic protocols, including Identity-Based Encryption (IBE), digital signatures, Zero-Knowledge Proofs (ZKP), and Attribute-Based Encryption (ABE). The Miller Loop enables efficient computation of these pairings, which would otherwise be computationally expensive.

1.1 Bilinear Pairings

In cryptography, a bilinear pairing is a mapping:

$$e:G_{1} \times G_{2} \rightarrow G_{T}$$

where: -$G_{1}$ and $G_{2}$ are elliptic curve groups defined over a finite field. -$G_{T}$ is the target group, typically a multiplicative group of a finite field.

1.2 Properties of Bilinear Pairings

• Bilinearity: $e(aP,bQ) = e(P,Q)^{ab}$ for any points $P \in G_{1}$ and $Q \in G_{2}$, and scalars $a,b \in Z$.
• Non-degeneracy: There exist points $P \in G_{1}$ and $Q \in G_{2}$ such that $e(P,Q) \neq 1$.
• Computability: Computing the pairing $e(P,Q)$ must be feasible, which is precisely the role of the Miller Loop.

2. Principles of the Miller Loop

To compute $e(P,Q)$, a bivariate polynomial is constructed based on the coordinates of $P$, and then evaluated at the coordinates of $Q$:

$$e(P,Q) = f_{r}\left( Q_{x},Q_{y} \right)^{\frac{q^{k} - 1}{r}}$$

where:

• $p$ is the prime order of the finite field,
• $r$ is the order of the elliptic curve subgroup,
• $k$ is the embedding degree.

The function $f_{r}$ follows the recursive relation:

$$f_{1} = 1,$$

$$f_{i + 1} = f_{i} \cdot l_{(iP,P)}(Q),$$

$$f_{i} = f_{i/2}^{2} \cdot l_{(i/2P, - iP)}(Q)$$

where:

• $l_{R,S}(Q)$ represents the evaluation of the line equation passing through points $R$ and $S$ at $Q$.
• $\frac{q^{k} - 1}{r}$ is known as Final Exponentiation, applied after computing $f_{r}\left( Q_{x},Q_{y} \right)$.

Using the recursive relation, $f_{r}\left( Q_{x},Q_{y} \right)$ can be simplified. For example, if $r = 9$:

$$f_{9} = f_{8} \cdot l_{(8P,P)}(Q)$$

$$= f_{4}^{2} \cdot l_{(4P, - 8P)}(Q) \cdot l_{(8P,P)}(Q)$$

$$= \left( \left( f_{2}^{2} \cdot l_{(2P, - 4P)}(Q) \right)^{2} \cdot l_{(4P, - 8P)}(Q) \right) \cdot l_{(8P,P)}(Q)$$

$$= l_{(P, - 2P)}^{4}(Q) \cdot l_{(2P, - 4P)}^{2}(Q) \cdot l_{(4P, - 8P)}(Q) \cdot l_{(8P,P)}(Q)$$

3. Optimizations for the Miller Loop

The Miller Loop is the core algorithm for computing bilinear pairings. Several optimization techniques can significantly reduce computation time and improve efficiency.

3.1 Precomputation

Precomputation reduces redundant calculations by storing frequently used point multiples in advance. In the Miller Loop, precomputing multiples of a point (such as $2P,3P,\ldots,kP$) reduces the number of doublings and additions.

For example, given a point $P \in G_{1}$ and scalar $k$, we can precompute:

$$P_{i} = iP\quad for\quad i \in \{ 1,2,\ldots,m\}$$

where $m$ is the number of precomputed values. During computation, these precomputed values can be used directly instead of recalculating multiples each time.

3.2 Windowing Method

The windowing method reduces the number of doublings and additions by processing multiple bits of a scalar at a time. Given a scalar $k$ with binary representation $k = \sum_{i = 0}^{n - 1}k_{i}2^{i}$, where $k_{i} \in \{ 0,1\}$:

• Instead of processing one bit at a time, we process $w$ bits in each step.
• Suppose $w = 3$, we precompute values like $P,2P,3P,4P,5P$, and use them during computations.
• The scalar can be rewritten as $k = \sum_{i = 0}^{m - 1}k'_{i}2^{w \cdot i}$, where $k'_{i}$ is the value within each window.

Optimization effect: With window size $w$, each iteration processes $w$ bits, reducing the total number of iterations to $\frac{n}{w}$, significantly decreasing the number of doublings and additions.

3.3 Optimal Curve Selection

Choosing optimal elliptic curves can further accelerate bilinear pairing computations. Pairing-friendly curves are specifically designed to optimize pairing operations.

For example, for an elliptic curve $E$ defined over $F_{q}$, if the order of the curve is $r$ and $r$ follows a specific structure (such as $r = 2^{n} + 1$), it can greatly optimize computations.

Advantages of pairing-friendly curves:

On such curves, the Miller Loop runs more efficiently, particularly for Tate and Weil pairings, which require mappings between groups $G_{1}$ and $G_{2}$.

Common pairing-friendly curves include BN curves (Barreto-Naehrig curves) and BLS curves (Barreto-Lynn-Scott curves), which leverage special order structures to eliminate redundant computations.

3.4 Frobenius Endomorphisms

Frobenius endomorphisms leverage the special properties of elliptic curves over finite fields to accelerate the Miller Loop computation. For a curve $E$ defined over a finite field $F_{q}$, the Frobenius map $\varphi$ acts on a point $P$ as follows:

$$\varphi(P) = P^{q}$$

The properties of the Frobenius map can be utilized within the Miller function to enhance performance, particularly when computing the Tate pairing. By applying the Frobenius endomorphism during the Miller Loop, unnecessary operations can be reduced.

Optimization Effect: Using Frobenius endomorphisms reduces the number of multiplications in the Miller Loop, especially when mapping to the target group $G_{T}$.

3.5 Efficient Scalar Multiplication Algorithms

Scalar multiplication is a core operation in the Miller Loop, and optimizing scalar multiplication algorithms can accelerate the overall computation.

• Montgomery Multiplication: Montgomery multiplication speeds up scalar multiplication by avoiding intermediate storage and expensive division operations. Given a scalar $k$ and a point $P$, using the Montgomery method to compute $kP$ reduces computational complexity.
• Pippenger's Algorithm: Pippenger's algorithm is an efficient multi-point scalar multiplication method, particularly useful when multiple scalar multiplications are required. By optimizing windowing and decomposition techniques, it minimizes computational steps.
• Optimization Effect: These scalar multiplication algorithms effectively reduce the number of multiplications in the Miller Loop, thereby speeding up the computation.

3.6 Pairing Optimization

In the Miller Loop, pairing computation optimizations often focus on reducing redundant steps or improving the mapping process.

• Selective Mapping Optimization: For the Tate pairing, techniques such as trace mapping and anti-trace mapping can efficiently map points from $G_{2}$ back to $G_{1}$, thereby reducing computational complexity.

For example, the Tate pairing computation follows:

$$e(P,Q) = \prod_{i = 0}^{n - 1}\left( double - and - add\left( P,k_{i} \right) \right)$$

By applying trace mapping (mapping elements from $G_{2}$ efficiently), the computational complexity can be significantly reduced.

Optimization Effect: Selective mapping optimization reduces unnecessary steps in the Miller Loop, improving computational efficiency.

3.7 Parallelization

Parallelization accelerates the Miller Loop by distributing computational tasks across multiple processing units or cores. In large-scale cryptographic applications, parallel computing techniques can significantly reduce execution time.

If the Miller Loop requires $n$ point doubling and addition operations, parallelization can distribute the workload among $p$ processing units, each handling $\frac{n}{p}$ operations, thus speeding up the entire process.

For example, if the Miller Loop requires $n$ point doubling and addition operations, using parallel computation with $p$ processing units reduces the computation time to:

$$T_{parallel} = \frac{T_{serial}}{p}$$

where $T_{serial}$ is the execution time for single-threaded computation.

Optimization Effect: Parallelization significantly enhances the performance of the Miller Loop, particularly when utilizing multi-core CPUs or GPU acceleration.

3.8 Summary of Optimization Techniques

The following optimization methods can significantly improve the efficiency of the Miller Loop:

1. Precomputation: Precompute commonly used multiples to reduce redundant calculations.
2. Windowing Method: Process multiple scalar bits at once, reducing the number of doublings and additions.
3. Optimal Curve Selection: Choose pairing-friendly curves to optimize pairing computation.
4. Frobenius Endomorphisms: Use Frobenius mapping to accelerate computations.
5. Efficient Scalar Multiplication Algorithms: Apply Montgomery or Pippenger’s algorithm to optimize scalar multiplication.
6. Pairing Optimization: Reduce redundant computations via optimized mapping techniques.
7. Parallelization: Use parallel computing to accelerate the Miller Loop.

These optimization techniques are often combined based on practical application requirements to achieve optimal performance.

4. Conclusion

The Miller Loop is a fundamental algorithm in modern cryptographic systems, particularly in protocols that rely on bilinear pairings. By efficiently computing pairings between elliptic curve points, the Miller Loop enables the implementation of complex cryptographic protocols, such as identity-based encryption, digital signatures, and zero-knowledge proofs.

Through optimizations such as precomputation, windowing, and efficient scalar multiplication, the performance of the Miller Loop can be significantly improved, making it suitable for large-scale cryptographic applications.