Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings

Craig Costello, Kristin E. Lauter, Michael Naehrig

TL;DR

This paper introduces four specific "subfamilies" of Barreto-Lynn-Scott (BLS) curves that significantly simplify and accelerate the implementation of high-security pairings. By focusing on particular mathematical properties of these curves, the authors provide a roadmap for cryptographers to achieve more efficient and robust pairing-based cryptography.

What Problem Does This Paper Address?

Pairing-based cryptography, a powerful tool for advanced cryptographic schemes, relies on complex mathematical operations called "pairings." While Barreto-Naehrig (BN) curves have been the go-to for 128-bit security, the push for higher security levels (like 256-bit and beyond) necessitates the use of different elliptic curve families, such as the Barreto-Lynn-Scott (BLS) curves. However, optimizing pairings for these new curve families presents challenges. Specifically, finding the "right" BLS curves that offer both high security and efficient implementation is a non-trivial task. This paper aims to solve this by identifying specific, highly efficient subfamilies of BLS curves that streamline the implementation process.

Methods

The authors' core contribution lies in identifying specific mathematical constraints on the parameters used to generate BLS curves. Instead of searching through all possible parameters, they focus on four particular congruence classes for a search parameter, denoted as $x_0$. This specialization leads to several key advantages:

  • Simplified Curve Definition: The curve's coefficients and its "twist" (a related curve crucial for pairing computations) are automatically determined, eliminating computational effort.
  • Efficient Field Arithmetic: The chosen parameters result in prime fields that support highly efficient "towering options" for the necessary extension fields, which are critical for pairing performance.
  • Optimized Pairing Operations: The specific choices of $x_0$ directly translate to more efficient Miller loops and final exponentiation, the two main computational stages of a pairing.

The paper rigorously proves these advantages through mathematical lemmas and propositions, demonstrating how these specific subfamilies offer immediate efficiency gains.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and provides example curves, rather than training on or evaluating against specific datasets.

Key Insights and Ideas

  • The Power of Specialization: The paper highlights that by restricting the search space for curve parameters to just four specific congruence classes, one can unlock significant and consistent efficiency gains across the board. This is a powerful demonstration of how targeted mathematical analysis can yield practical cryptographic improvements.
  • "Implementation-Friendly" is Key: The authors emphasize that their chosen subfamilies are not just theoretically efficient but also simplify the implementation process. This is crucial for real-world deployment where ease of coding and reduced complexity can prevent errors and speed up development.
  • Automatic Determination of Curve Properties: The fact that the curve coefficients and twists are automatically determined by the choice of $x_0$ is a major win for implementers. It removes guesswork and potential errors in curve selection.
  • Field Tower Optimization: The paper shows that these specific BLS curves naturally lead to efficient field tower constructions, which are essential for fast arithmetic in the large finite fields used in pairings.

Key Results

The paper identifies four "attractive subfamilies" of BLS curves, characterized by the search parameter $x_0$ belonging to specific congruence classes modulo 72 (namely $x_0 \equiv 7, 16, 31, 64 \pmod{72}$). For these subfamilies, the authors demonstrate:

  • Immediate Curve and Twist Definition: The curve constant $b$ and the correct sextic twist are immediately determined, saving computational effort.
  • Efficient Field Tower Options: Proposition 2 outlines three distinct and efficient ways to construct the necessary extension fields ($F_{p^2}, F_{p^4}, F_{p^8}, F_{p^{12}}, F_{p^{24}}$).
  • Examples for High Security: The paper provides extensive tables (Tables 4-7) listing example BLS curves for various security levels (192-bit to 320-bit), with parameters optimized for low Hamming weight and efficient representation. These tables serve as a valuable resource for implementers.

Limitations and Future Work

The authors acknowledge that while their chosen subfamilies offer consistent advantages, other congruency classes might, in specific instances, produce curves with similar performance. However, their argument is that the four identified classes guarantee these advantages across the board.

Future work could involve further exploring the trade-offs between different field tower options and twist choices for specific implementation scenarios. The paper also implicitly suggests that further research into optimizing the "hard part" of the final exponentiation, as detailed in Section 5, will continue to yield performance improvements. The provided tables of example curves are a direct resource for implementers looking to leverage these findings.

Summary updated

BibTeX
@article{costello2011attractive,
  author = {Craig Costello and Kristin E. Lauter and Michael Naehrig},
  title = {{Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
}

Loading related content...

Figure