Implementation of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide two cyclic groups G₁ and G₂, with an efficient bilinear pairing:

e: G₁ × G₂ → G_T

Pairing

Let G₁, G₂ and G_T be abelian groups of prime order q and let g and h elements of G₁ and G₂ respectively . A pairing is a non-degenerate bilinear map e: G₁ × G₂ → G_T.

This bilinearity property is what makes pairings such a powerful primitive in cryptography. It satisfies:

• e(g₁ + g₂, h) = e(g₁, h) e(g₂, h)
• e(g, h₁ + h₂) = e(g, h₁) e(g, h₂)

The non-degeneracy property guarantees non-trivial pairings for non-trivial arguments. In other words, being non-degenerate means that:

• ∀ g ≠ 1, ∃ h_i ∈ G₂ such that e(g, h_i) ≠ 1
• ∀ h ≠ 1, ∃ g_i ∈ G₁ such that e(g_i, h) ≠ 1

An example of a pairing would be the scalar product on euclidean space <.> : Rⁿ × Rⁿ → R

Example Usage

A simple example of calculating the optimal ate pairing given two points in G₁ and G₂.

import Protolude

import Pairing.Group
import Pairing.Pairing
import Pairing.Point
import Pairing.Fq (Fq(..))
import Pairing.Fq2 (Fq2(..))

e1 :: G1
e1 = Point
        (Fq 1368015179489954701390400359078579693043519447331113978918064868415326638035)
        (Fq 9918110051302171585080402603319702774565515993150576347155970296011118125764)


e2 :: G2
e2 = Point
        (Fq2
         (Fq 2725019753478801796453339367788033689375851816420509565303521482350756874229)
          (Fq 7273165102799931111715871471550377909735733521218303035754523677688038059653 )
          )
        (Fq2
         (Fq 2512659008974376214222774206987427162027254181373325676825515531566330959255)
         (Fq 957874124722006818841961785324909313781880061366718538693995380805373202866)
        )


main :: IO ()
main  = do
  putText "Ate pairing:"
  print (atePairing e1 e2)
  let 
    lhs = reducedPairing (gMul e1 2) (gMul e2 3)
    rhs = (reducedPairing e1 e2)^(2 * 3)
  putText "Is bilinear:" 
  print (lhs == rhs)

Pairings in cryptography

Pairings are used in encryption algorithms, such as identity-based encryption (IBE), attribute-based encryption (ABE), (inner-product) predicate encryption, short broadcast encryption and searchable encryption, among others. It allows strong encryption with small signature sizes.

Admissible Pairings

A pairing e is called admissible pairing if it is efficiently computable. The only admissible pairings that are suitable for cryptography are the Weil and Tate pairings on algebraic curves and their variants. Let r be the order of a group and E[r] be the entire group of points of order r on E(F_q). E[r] is called the r-torsion and is defined as E[r] = { P ∈ E(F_q) | rP = O }. Both Weil and Tate pairings require that P and Q come from disjoint cyclic subgroups of the same prime order r. Lagrange's theorem states that for any finite group G, the order (number of elements) of every subgroup H of G divides the order of G. Therefore, r | #E(F_q).

G₁ and G₂ are subgroups of a group defined in an elliptic curve over an extension of a finite field F_q, namely E(F_q^k), where q is the characteristic of the field and k is a positive integer called embedding degree.

The embedding degree k plays a crucial role in pairing cryptography:

• It's the value that makes F_q^k be the smallest extension of F_q such that E(F_q^k) captures more points of order r.
• It's the minimal value that holds r | (q^k - 1).
• It's the smallest positive integer such that E[r] ⊂ E(F_q^k)

There are subtle but relevant differences in G₁ and G₂ subgroups depending on the type of pairing. Nowadays, all of the state-of-the-art implementations of pairings take place on ordinary curves and assume a type of pairing (Type 3) where G₁ = E[r] ∩ Ker(π - [1]) and G₂ = E[r] ∩ Ker(π - [q]) and there is no non-trivial map φ: G₂ → G₁.

Tate Pairing

The Tate pairing is a map:

tr : E(F_q^k)[r] × E(F_q^k) / rE(F_q^k) → F^*_q^k / (F^*_q^k)^r

defined as:

tr(P, Q) = f(Q)

where P ∈ E(F_q^k)[r], Q is any representative in a equivalence class in E(F_q^k) / rE(F_q^k) and F^*_q^k / (F^*_q^k)^r is the set of equivalence classes of F^*_q^k under the equivalence relation a ≡ b iff a / b ∈ (F^*_q^k)^r. The equivalence relation in the output of the Tate pairing is unfortunate. In cryptography, different parties must compute the same value under the bilinearity property.

The reduced Tate pairing solves this undesirable property by exponentiating elements in F^*_q^k / (F^*_q^k)^r to the power of (q^k - 1) / r. It maps all elements in an equivalence class to the same value. It is defined as:

Tr(P, Q) = t_r(P, Q)^{#F_qk / r} = f_r,P(Q)^{(qk - 1) / r}.

When we say Tate pairing, we normally mean the reduced Tate pairing.

Pairing optimization

Tate pairings use Miller's algorithm, which is essentially the double-and-add algorithm for elliptic curve point multiplication combined with evaluation of the functions used in the addition process. Miller's algorithm remains the fastest algorithm for computing pairings to date.

Both G₁ and G₂ are elliptic curve groups. G_T is a multiplicative subgroup of a finite field. The security an elliptic curve group offers per bit is considerably greater than the security a finite field does. In order to achieve security comparable to 128-bit security (AES-128), an elliptic curve of 256 bits will suffice, while we need a finite field of 3248 bits. The aim of a cryptographic protocol is to achieve the highest security degree with the smallest signature size, which normally leads to a more efficient computation. In pairing cryptography, significant improvements can be made by keeping all three group sizes the same. It is possible to find elliptic curves over a field F_q whose largest prime order subgroup r has the same bit-size as the characteristic of the field q. The ratio between the field size q and the large prime group order r is called the φ-value. It is an important value that indicates how much (ECDLP) security a curve offers for its field size. φ=1 is the optimal value. The Barreto-Naehrig (BN) family of curves all have φ=1 and k=12. They are perfectly suited to the 128-bit security level.

Most operations in pairings happen in the extension field F_q^k. The larger k gets, the more complex F_q^k becomes and the more computationally expensive the pairing becomes. The complexity of Miller's algorithm heavily depends on the complexity of the associated F_q^k-arithmetic. Therefore, the aim is to minimize the cost of arithmetic in F_q^k.

It is possible to construct an extension of a field F_q^k by successively towering up intermediate fields F_q^a and F_q^b such that k = a^i b^j, where a and b are usually 2 and 3. One of the reasons tower extensions work is that quadratic and cubic extensions (F_q² and F_q³) offer methods of performing arithmetic more efficiently.

Miller's algorithm in the Tate pairing iterates as far as the prime group order r, which is a large number in cryptography. The ate pairing comes up as an optimization of the Tate pairing by shortening Miller's loop. It achieves a much shorter loop of length T = t - 1 on an ordinary curve, where t is the trace of the Frobenius endomorphism. The ate pairing is defined as:

at(Q,P) = f_r,Q(P)^{(qk - 1) / r}

Implementation

We have implemented the optimal Ate pairing over the BN128 curve, i.e. we define q and r as

• q = 36t⁴ + 36t³ + 24t² + 6t + 1
• r = 36t⁴ + 36t³ + 18t² + 6t + 1
• t = 4965661367192848881

The tower of finite fields we work with is defined as follows:

• F_q is the prime field with characteristic q
• F_q² := F_q[u]/u² + 1
• F_q⁶ := F_{q²[v]/v³ - (9 + u)}
• F_q¹² := F_q⁶[w]/w² - v

The groups' definitions are:

• G₁ := E(F_q), with equation y² = x³ + 3
• G₂ := E'(F_q²), with equation y² = x³ + 3 / (9 + u)
• G_T := μ_r, i.e. the r-th roots of unity subgroup of the multiplicative group of F_q¹²

License

Copyright (c) 2018-2019 Adjoint Inc.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
OR OTHER DEALINGS IN THE SOFTWARE.