Pairing-based-cryptography

Note: This is an experimental implementation of optimal Ate pairing in Java. It has never been used in production. Use it at your risk.

Introduction

Introduction to Parings

An admissible bilinear pairing is a function , where and are cyclic subgroups of elliptic curve groups, is a cyclic subgroup of the multiplicative group of a finite field, , and have order r, and the following conditions hold:

• Bilinearity: for and , and

• Non-degeneracy: $e(P, R) \neq 1$ for some $P \in \mathbb{G}_1$ and $R \in \mathbb{G}_2$. Or, equivalently, $e(P, R) = 1$ for all $R \in \mathbb{G}_2$ if and only if $P = \mathcal{O}$; and $e(P, R) = 1$ for all $P \in \mathbb{G}_1$ if and only if $R = \mathcal{O}$.\

Also, it immediately follows that $e(aP, bR)=e(P, R)^{ab}=e(bP, aR)$ for any two integers a and b.

Barreto - Naehrig curves

A BN curve is an elliptic curve over a finite prime field , with prime order n and embedding degree k = 12.

The equation of the curve is

The curve order and the characteristic of are parameterised as:

Hence the trace (of Frobenius) of the curve

with

Finding b is actually very simple: take the smallest b ≠ 0 such that b + 1 is a quadratic residue modp and the point , which is clearly on the curve. [3]