tate-bilinear-pairing 1.0

A Python library for calculating Tate bilinear pairing on the super-singular elliptic curve E: y² = x³ - x + 1 over GF(3^m)

Introduction

This package is a Python library for calculating the Tate bilinear pairing, especially on the super-singular elliptic curve $E:y^2=x^3-x+1$ in affine coordinates over the Galois Field $\text{GF}(3^m)$. The largest order of $G_1$ supported is 911 bits.

It also provides functions for:

• Point addition on the elliptic curve group
• Scalar multiplication ($k \cdot P$).

The Tate pairing implementation follows the paper by Beuchat et al. [3], while the elliptic curve group operations follow Kerins et al. [2].

This package is in Pure Python., working with Python 2.7 and 3.2+.

Performance: One Tate bilinear pairing takes approximately 3.26 seconds on an Intel Core2 L7500 (1.60 GHz) when $|G_1| = 151$ bits.

---

What is Tate bilinear pairing?

The Tate bilinear pairing is a map that takes two points on an elliptic curve and outputs a nonzero element in the extension field $\text{GF}(3^{6m})$.

The most efficient method for computing it in characteristic three is the $\eta_T$ pairing, introduced by Barreto et al.

For more information, see references [1], [2], [3], and [4].

---

Usage

1. Tate Bilinear Pairing

from tate_bilinear_pairing import eta

# Initialize for 151-bit order of G1
eta.init(151)

import random
a = random.randint(0, 1000)
b = random.randint(0, 1000)

from tate_bilinear_pairing import ecc
g = ecc.gen()

inf1, x1, y1 = ecc.scalar_mult(a, g)
inf2, x2, y2 = ecc.scalar_mult(b, g)

# Compute Tate pairing
t = eta.pairing(x1, y1, x2, y2)

---

2. Point Addition

# p1 = [inf1, x1, y1]
# p2 = [inf2, x2, y2]
p3 = ecc.add(p1, p2)

---

3. Scalar Multiplication

k = random.randint(0, 1000)
p3 = ecc.scalar_mult(k, p1)

---

References

[1] I. Duursma, H.S. Lee. Tate pairing implementation for hyper-elliptic curves $y^2=x^p-x+d$. Advances in Cryptology - Proc. ASIACRYPT ’03, pp. 111-123, 2003.

[2] T. Kerins, W.P. Marnane, E.M. Popovici, and P.S.L.M. Barreto. Efficient hardware for the Tate pairing calculation in characteristic three. Cryptographic Hardware and Embedded Systems - Proc. CHES ’05, pp. 412-426, 2005.

[3] J. Beuchat, N. Brisebarre, J. Detrey, E. Okamoto, M. Shirase, and T. Takagi. Algorithms and Arithmetic Operators for Computing the $\eta_T$ Pairing in Characteristic Three. IEEE Transactions on Computers, Special Section on Special-Purpose Hardware for Cryptography and Cryptanalysis, vol. 57 no. 11 pp. 1454-1468, 2008.

[4] P.S.L.M. Barreto, S.D. Galbraith, C. O hEigeartaigh, and M. Scott, Efficient Pairing Computation on Supersingular Abelian Varieties. Designs, Codes and Cryptography, vol. 42, no. 3, pp. 239-271, Mar. 2007.