BN254 is pairing friendly

BN254는 중요한 키워드이다. 특히 이 곡선은 BLS12-381과 더불어 가장 널리 쓰이고 뭐든 이해하는데 기본이 된다. 간단한 조사를 하여 결과를 남기고,

BN254 is a pairing-friendly elliptic curve. It belongs to the Barreto-Naehrig (BN) family of curves, which are known for their efficiency in cryptographic pairings, particularly in protocols like zero-knowledge proofs, identity-based encryption, and attribute-based encryption. BN254 is specifically designed to support optimal pairing operations efficiently.

Characteristics of BN254:

1. Prime Order Group: BN254 has a 254-bit prime order, which is why it's often referred to as "BN254". The prime order offers a high level of security while maintaining efficiency.

2. Weierstrass Equation: BN254 is defined over a finite field $F_p$ and typically takes the following form:

   $E: y^2 = x^3 + b$

   where $b$ is a constant.

3. Embedding Degree: BN254 has an embedding degree of 12, meaning that when you compute a pairing on this curve, you map the problem to a finite field extension of degree 12, which balances security and efficiency.

4. Optimal Ate Pairing: BN254 curves are particularly efficient for computing Ate pairings. The Ate pairing computation is faster compared to traditional Weil or Tate pairings, which is one reason the BN family is favored in many cryptographic schemes.

Cryptographic Pairings

Cryptographic pairings are bilinear maps, typically denoted by:

Where:

• $G_1$ and $G_2$ are elliptic curve groups.
• $G_T$ is a finite field (often a multiplicative group of a finite field).
• The map $e$ has properties such as bilinearity, non-degeneracy, and computability.

Example of a Pairing on BN254

For the BN254 curve, a common choice is:

• $G_1$ is a subgroup of points on the elliptic curve defined over $F_p$.
• $G_2$ is a subgroup of the same elliptic curve but defined over a quadratic extension of the field, $F_{p^2}$.
• $G_T$ is a multiplicative group of $F_{p^{12}}$.

A simplified example of how a pairing could be used with the BN254 curve is in identity-based encryption (IBE):

1. Setup: The trusted authority chooses a generator $g \in G_1$, a secret key $s \in \mathbb{Z}_p$, and computes $g^s \in G_1$.

2. Key Extraction: To generate a private key for a user with identity $ID$, the authority computes $H(ID)^s$, where $H(ID)$ is a hash function mapping the identity into $G_1$.

3. Encryption: Given a public key $g \in G_1$, a sender can encrypt a message $M$ by computing the pairing $e(g^s, H(ID))$.

4. Decryption: The recipient can decrypt the message by leveraging the bilinearity property of the pairing, which allows them to recover the correct pairing result and decrypt the message.

Why BN254 is Pairing-Friendly

1. Efficiency: BN254 supports optimal Ate pairings, which are much faster than traditional pairings.

2. Security: The 254-bit prime order and embedding degree of 12 offer 128-bit security, which is suitable for many cryptographic applications today.

3. Applications: BN254 is widely used in privacy-focused applications like zk-SNARKs (zero-knowledge succinct non-interactive arguments of knowledge) and various other blockchain technologies.

Example Calculation

Assume you have two points $P \in G_1$ and $Q \in G_2$, and you want to compute a pairing:

The bilinearity property ensures:

This property is crucial for protocols like BLS signatures, where verifying a signature requires pairing operations.

Conclusion

BN254 is an efficient pairing-friendly elliptic curve, widely adopted due to its balance of security and speed. Its construction supports fast Ate pairings, making it a preferred choice in many cryptographic protocols.