Contents

‍

1. Bilinear Pairing

Bilinear pairing is a mathematical concept used in cryptography, particularly in the design and analysis of various cryptographic protocols such as identity-based encryption, digital signatures, and zero-knowledge proofs. Bilinear pairing provides a method for constructing new cryptographic primitives, enabling more efficient algorithms and novel structures.

1.1 Definition

A bilinear pairing is a function $e:G_{1} \times G_{2} \rightarrow G_{T}$ that takes elements from two groups $G_{1}$ and $G_{2}$ and maps them to a target group $G_{T}$, satisfying the following properties:

1. Bilinearity: For any $g_{1},g_{1}' \in G_{1}$ and $g_{2},g_{2}' \in G_{2}$, it holds that:

$$e\left( g_{1}^{a},g_{2}^{b} \right) = e\left( g_{1},g_{2} \right)^{ab}$$

where $a,b$ are arbitrary integers. This property ensures that the function is linear in both arguments.

2. Non-degeneracy: There exists a pair $\left( g_{1},g_{2} \right) \in G_{1} \times G_{2}$ such that $e\left( g_{1},g_{2} \right) \neq 1$. This condition ensures that the pairing is non-trivial and does not map all pairs to the identity element in $G_{T}$.

3. Computability: The function $e$ must be efficiently computable for all elements in $G_{1}$ and $G_{2}$.

1.2 Types of Bilinear Pairings

• Weil Pairing: Commonly used in elliptic curve cryptography, particularly in constructing pairing-based cryptographic protocols such as identity-based encryption (IBE). Weil pairing is defined on elliptic curves and provides an efficient method for mapping points on the curve to a finite field.
• Tate Pairing: Similar to Weil pairing, Tate pairing is another bilinear pairing used in elliptic curves. In some contexts, it is more efficient than Weil pairing and is frequently used in cryptographic protocols.
• Optimal Pairing: These pairings are defined in the context of elliptic curves, where the choice of groups $G_{1}$, $G_{2}$, and $G_{T}$ allows for efficient computation. A common example is the BN curve (Barreto-Naehrig curve), which is widely used in pairing-based cryptography.

2. Classification of Bilinear Mappings

The classification of bilinear mappings primarily depends on the selection of groups $G_{1}$ and $G_{2}$, as well as their mapping characteristics. Factors influencing classification include whether random sampling of points in $G_{2}$ is feasible and whether an isomorphic mapping from $G_{2}$ to $G_{1}$ exists to ensure security.

2.1 Type 1 Pairing

In Type 1 pairings, the bilinear mapping $e$ is defined on an elliptic curve $E$ with a supersingular group. In this case, there exists a mapping that can transform $G_{1}$ into an external group. The pairing is defined as follows:

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

• Advantages: The structure of supersingular curves allows for some simplified constructions.
• Disadvantages: The computational efficiency is lower in large-scale applications, leading to performance bottlenecks.

2.2 Type 2 Pairing

In Type 2 pairings, $G_{2}$ is chosen from a subgroup of the elliptic curve $E\lbrack r\rbrack$, excluding certain subgroups $R_{1}$ and $R_{2}$. Using trace mapping, $G_{2}$ can be mapped back to $G_{1}$, while anti-trace mapping allows for mapping $G_{2}$ back to $R_{2}$. This structure does not support random sampling in $G_{2}$.

• Advantages: Relatively simple and easy to implement, making it suitable for some protocols.
• Disadvantages: The inability to randomly sample points in $G_{2}$ limits protocol flexibility and does not fully meet the randomness requirements of certain cryptographic schemes.

2.3 Type 3 Pairing

In Type 3 pairings, $G_{2}$ is chosen as $R_{2}$, allowing for random sampling in $G_{2}$. A point can first be randomly selected in $R_{2}$ and then converted into a point in $E\lbrack r\rbrack$ using a cofactor multiplication. The point can then be mapped to $G_{2}$ using anti-trace mapping.

• Advantages: Allows for random sampling in $G_{2}$, increasing flexibility and protocol scalability.‍
• Disadvantages: Although random sampling is possible, efficiency issues still arise, especially in larger groups.

2.4 Type 4 Pairing

In Type 4 pairings, $G_{2}$ is chosen as the entire group $E\lbrack r\rbrack$. This method provides the most flexible sampling approach, allowing free selection of any point in $G_{2}$.

• Advantages: Offers complete freedom in random sampling within $G_{2}$, making it highly adaptable and well-suited for complex protocols.
• Disadvantages: Computational overhead can be significant, potentially leading to performance bottlenecks in implementation and optimization.

The classification of bilinear pairings depends primarily on the choice of groups $G_{1}$ and $G_{2}$ and their mapping characteristics. Different types of pairings involve trade-offs between security, computational efficiency, and protocol flexibility. Understanding and selecting the appropriate bilinear pairing type is crucial when designing cryptographic protocols, especially when balancing efficiency and security.

3. Cryptographic Applications of Bilinear Pairings

1. Identity-Based Encryption (IBE): Bilinear pairings enable deriving a user's public key directly from their identity (such as an email address), eliminating the need for certificates and Public Key Infrastructure (PKI).

2. Short Signatures: Pairing-based cryptography allows for the construction of cryptographic signatures that are shorter than traditional RSA or DSA signatures, making storage and transmission more efficient.

3. Zero-Knowledge Proofs (ZKP): Bilinear pairings are used in zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) and other forms of zero-knowledge proofs, allowing one party to prove the validity of a statement without revealing any information about it.

4. Attribute-Based Encryption (ABE): In ABE, a user's ability to decrypt data is determined by their attributes (such as roles or permission levels). Bilinear pairings enable the construction of more efficient attribute-based systems.

5. Multi-Party Computation (MPC): Pairings are also used in protocols that allow multiple parties to jointly compute a result without revealing their individual inputs, ensuring privacy.

4. Conclusion

Bilinear pairings serve as the foundation for constructing efficient, secure, and scalable cryptographic protocols. They enable advanced cryptographic functionalities such as identity-based encryption, attribute-based encryption, and zero-knowledge proofs, making them indispensable tools in modern cryptography, especially when traditional methods fail to provide sufficient efficiency or security guarantees.