3.4 Pairing-based cryptography

Pairing-based cryptography uses bilinear maps on elliptic curves to create advanced cryptographic schemes. These pairings, like the Weil and Tate pairings, enable new security features by leveraging the algebraic structure of elliptic curves.

This approach opens up possibilities for identity-based encryption, short signatures, and other novel protocols. However, it also brings challenges in curve selection, efficiency optimization, and balancing security with performance in real-world implementations.

Bilinear pairings on elliptic curves

• Bilinear pairings are mathematical functions that map pairs of points on an elliptic curve to elements in a finite field
• Pairings enable the construction of advanced cryptographic schemes by leveraging the algebraic structure of elliptic curves
• Two main types of pairings used in cryptography are the Weil pairing and the Tate pairing

Weil pairing

Definition of Weil pairing

• The Weil pairing is a bilinear map that takes two points on an elliptic curve and outputs an element in a finite field
• Denoted as $e_n: E[n] \times E[n] \rightarrow \mu_n$, where $E[n]$ is the $n$-torsion subgroup and $\mu_n$ is the group of $n$-th roots of unity
• Satisfies bilinearity, non-degeneracy, and alternating properties

Properties of Weil pairing

• Bilinearity: $e_n(P_1 + P_2, Q) = e_n(P_1, Q) \cdot e_n(P_2, Q)$ and $e_n(P, Q_1 + Q_2) = e_n(P, Q_1) \cdot e_n(P, Q_2)$
• Non-degeneracy: If $e_n(P, Q) = 1$ for all $Q \in E[n]$, then $P = \mathcal{O}$ (the point at infinity)
• Alternating: $e_n(P, P) = 1$ for all $P \in E[n]$
• Compatibility with isogenies: If $\phi: E_1 \rightarrow E_2$ is an isogeny, then $e_n(\phi(P), \phi(Q)) = e_n(P, Q)^{\deg(\phi)}$

Computation of Weil pairing

• The Weil pairing can be computed using Miller's algorithm, which evaluates rational functions at divisors
• Involves computing line functions and evaluating them at points on the elliptic curve
• Requires careful selection of divisors and efficient arithmetic on the elliptic curve and finite field

Tate pairing

Definition of Tate pairing

• The Tate pairing is another bilinear map that takes points on an elliptic curve and outputs an element in a finite field
• Denoted as $e_T: E(\mathbb{F}q)[n] \times E(\mathbb{F}{q^k})/nE(\mathbb{F}{q^k}) \rightarrow \mathbb{F}{q^k}^/({\mathbb{F}_{q^k}^})^n$
• Maps a point in the $n$-torsion subgroup and a coset of $E(\mathbb{F}{q^k})$ to an element in the quotient group $\mathbb{F}{q^k}^/({\mathbb{F}_{q^k}^})^n$

Properties of Tate pairing

• Bilinearity: Similar to the Weil pairing, the Tate pairing satisfies bilinearity properties
• Non-degeneracy: The Tate pairing is non-degenerate in the sense that for any non-zero point $P \in E(\mathbb{F}q)[n]$, there exists a point $Q \in E(\mathbb{F}{q^k})$ such that $e_T(P, Q) \neq 1$
• Compatibility with isogenies: The Tate pairing is also compatible with isogenies between elliptic curves

Computation of Tate pairing

• The Tate pairing can be computed using Miller's algorithm, similar to the Weil pairing
• Involves evaluating rational functions at divisors and performing operations on the elliptic curve and finite field
• Requires careful selection of parameters and efficient implementations to achieve practical performance

Tate pairing vs Weil pairing

• The Tate pairing has some advantages over the Weil pairing in terms of computation and flexibility
• The Tate pairing can be computed more efficiently than the Weil pairing in certain cases
• The Tate pairing allows for a wider range of elliptic curves and subgroups to be used compared to the Weil pairing
• However, the Weil pairing has a simpler definition and can be easier to work with in some theoretical settings

Pairing-friendly elliptic curves

Supersingular curves

• Supersingular elliptic curves have a special structure that makes them suitable for pairing-based cryptography
• They have a large embedding degree, which determines the size of the finite field used in the pairing computation
• Examples of supersingular curves include curves over binary fields and curves with j-invariant 0 or 1728

Ordinary curves

• Ordinary elliptic curves can also be used for pairing-based cryptography, but they require more careful selection of parameters
• The embedding degree of ordinary curves is typically smaller than that of supersingular curves
• Suitable ordinary curves include MNT curves, BN curves, and KSS curves

Construction of pairing-friendly curves

• Constructing pairing-friendly elliptic curves involves finding curves with desirable properties for efficient pairing computation and security
• Methods for constructing pairing-friendly curves include the Cocks-Pinch method, the Dupont-Enge-Morain method, and the Brezing-Weng method
• The choice of construction method depends on the desired embedding degree, security level, and efficiency requirements

Security of pairing-based cryptography

Bilinear Diffie-Hellman problem

• The bilinear Diffie-Hellman (BDH) problem is a computational problem that underlies the security of many pairing-based cryptographic schemes
• Given $P, aP, bP, cP$ for some points $P$ on an elliptic curve and unknown scalars $a, b, c$, the BDH problem is to compute $e(P, P)^{abc}$
• The hardness of the BDH problem is assumed in the security proofs of various pairing-based protocols

Decisional bilinear Diffie-Hellman problem

• The decisional bilinear Diffie-Hellman (DBDH) problem is a decisional variant of the BDH problem
• Given $P, aP, bP, cP, Z$, the DBDH problem is to determine whether $Z = e(P, P)^{abc}$ or a random element in the target group
• The DBDH assumption states that solving the DBDH problem is computationally infeasible for any polynomial-time algorithm

Security reductions and assumptions

• The security of pairing-based cryptographic schemes is often proved by reducing the security to the hardness of the BDH or DBDH problem
• Other assumptions used in the security analysis of pairing-based cryptography include the $q$-strong Diffie-Hellman assumption and the external Diffie-Hellman assumption
• Reductions and assumptions provide a formal framework for analyzing the security of pairing-based protocols and relating them to well-studied computational problems

Applications of pairing-based cryptography

Identity-based encryption

• Identity-based encryption (IBE) is a type of public-key encryption where the public key is derived from a user's identity (email address, phone number)
• Pairings enable the construction of efficient IBE schemes, such as the Boneh-Franklin IBE scheme and the Cocks IBE scheme
• IBE simplifies key management and eliminates the need for public key certificates

Attribute-based encryption

• Attribute-based encryption (ABE) is a generalization of IBE where users' private keys and ciphertexts are associated with attributes or policies
• Pairings are used to construct expressive ABE schemes, such as ciphertext-policy ABE (CP-ABE) and key-policy ABE (KP-ABE)
• ABE enables fine-grained access control and supports complex access policies based on attributes

Short signatures

• Pairings can be used to construct short signature schemes, such as the Boneh-Lynn-Shacham (BLS) signature scheme
• BLS signatures are much shorter than traditional digital signatures (RSA, ECDSA) while providing comparable security
• Short signatures are useful in scenarios with limited bandwidth or storage, such as blockchain applications and IoT devices

Tripartite Diffie-Hellman key exchange

• Pairings enable the construction of three-party Diffie-Hellman key exchange protocols, such as the Joux protocol
• In a tripartite Diffie-Hellman key exchange, three parties can simultaneously compute a shared secret key without the need for multiple rounds of communication
• Tripartite key exchange has applications in secure multi-party computation and collaborative key establishment

Efficiency of pairing computations

Miller's algorithm

• Miller's algorithm is the fundamental algorithm for computing pairings on elliptic curves
• It involves evaluating rational functions at divisors and performing operations on the elliptic curve and finite field
• Miller's algorithm has a complexity of $O(\log n)$ for a pairing of order $n$, making it relatively efficient

Optimizations and improvements

• Various optimizations and improvements have been proposed to enhance the efficiency of pairing computations
• Techniques such as the use of affine coordinates, the employment of efficient arithmetic in the underlying field, and the exploitation of the twisted curve can significantly speed up pairing computations
• Preprocessing and precomputation techniques can also be used to reduce the online computation time of pairings

Comparison of pairing types

• The efficiency of pairing computations depends on the choice of pairing type (Weil pairing, Tate pairing, optimal pairings)
• Tate pairings are generally more efficient than Weil pairings due to their simpler definition and the ability to use distortion maps
• Optimal pairings, such as the Ate pairing and its variants (R-ate pairing, optimal Ate pairing), further improve the efficiency by reducing the loop length in Miller's algorithm
• The choice of pairing type depends on the specific requirements of the cryptographic protocol and the trade-offs between security, efficiency, and implementation complexity

Challenges in pairing-based cryptography

Selecting suitable curves and parameters

• Selecting suitable elliptic curves and parameters is crucial for the security and efficiency of pairing-based cryptography
• Factors to consider include the embedding degree, the size of the underlying field, the security level, and the existence of efficient algorithms for pairing computation
• Standardized curves, such as the BN curves and the BLS curves, provide well-studied options for pairing-friendly curves

Balancing security and efficiency

• Pairing-based cryptography often involves a trade-off between security and efficiency
• Higher security levels require larger key sizes and more complex computations, which can impact the performance of pairing-based protocols
• Techniques such as using asymmetric pairings and optimizing pairing computations can help balance security and efficiency
• It is important to carefully assess the security requirements and performance constraints of the specific application when designing pairing-based cryptographic schemes

Implementation considerations

• Implementing pairing-based cryptography requires careful consideration of various factors to ensure security and efficiency
• Side-channel attacks, such as timing attacks and power analysis attacks, can potentially leak sensitive information during pairing computations
• Countermeasures, such as constant-time implementations and randomization techniques, should be employed to mitigate side-channel vulnerabilities
• Efficient algorithms and libraries for elliptic curve arithmetic and finite field operations are essential for practical implementations of pairing-based cryptography
• Proper parameter validation, key management, and secure key storage are also important aspects of implementing pairing-based cryptographic protocols