Tiny Tate Bilinear Pairing

Description

Tiny Tate Bilinear Pairing core is for calculating Tate bilinear pairing.
In fact it is a special type of Tate bilinear pairing called reduced $\eta_T$ pairing.

Its features are:
* super-singular elliptic curve E:y^2=x^3-x+1
* the field is the Galois field GF(3^m),m=97 or 593
* the irreducible polynomial is x^97+x^12+2 or x^593+x^112+2
* the group size is 151 bits or 911 bits
* vendor independent code
* very low hardware cost (≤0.2 US dollar) if m=97
* released under Apache License v2.0

Document & Specification

Specification (low secure level, 151 bits group size)
Specification (high secure level, 911 bits group size)

Mathematical background

The reduced $η_T$ pairing is introduced by Barreto et.al.
There are at least two related nice papers:
[1] P.Barreto, S.Galbraith, C.O hEigeartaigh, and M.Scott. Efficient pairing computation on supersingular abelian varieties. in
Designs, Codes and Cryptography. Springer Netherlands, Mar. 2007, vol. 42(3), pp. 239–271.
[2] J.Beuchat, N.Brisebarre, J.Detrey, E.Okamoto, M.Shirase, and T.Takagi. Algorithms and arithmetic operators for computing the η_T pairing in characteristic three. in IEEE Transactions on Computers, Special Section on Special-Purpose Hardware for Cryptography and Cryptanalysis, 57(11):1454-1468, 2008.

Synthesis results (ISE)

Low secure level core

Device:	Xilinx Spartan 3 XC3S200-5PQ208
Number of Slice Flip Flops:	1,319
Number of 4 input LUTs:	3,028
Number of occupied Slices:	1,730
Number of bonded IOBs:	15
Minimum period:	10.455ns
Maximum Frequency:	95.6MHz

* Synthesis tool is Xilinx ISE 13.4.

Synthesis results (Quartus)

Low secure level core

Device:	Altera Cyclone II EP2C20F484C7
Total logic elements:	3,637
Dedicated logic registers:	1,310
Total memory bits:	25,984
Total pins:	15

* Synthesis tool is Altera Quartus II 11.1.

Speed

The low secure level core computes one Tate pairing in 1.05 milliseconds if with a 50MHz clock.

The high secure level core computes one Tate pairing in 20.0 milliseconds if with a 50MHz clock.

Hardware cost

Xilinx Spartan 3 XC3S200 FPGA is enough for the low secure level core.
The price of that FPGA is less than 0.2 USA dollar per piece in 2012.

Compared to "Tate Bilinear Pairing core"

	Tiny Tate Bilinear Pairing core	Tate Bilinear Pairing core
Device:	Xilinx Spartan 3 XC3S200	Xilinx Virtex 4 XC4VLX200
Number of Slice Flip Flops:	1,319	31,383
Number of 4 input LUTs:	3,028	47,083
Number of occupied Slices:	1,730	30,149
Computation time:	1.02ms	0.76 ms

* The cores both have same functionality.
* The cores both have a low secure level. The group size is 151 bits.

Improvement

This core follows the idea in the academic paper of Mr.Beuchat et.al.
This core uses 20% less FPGA slices, 50% less RAM memory than Mr.Beuchat et.al.
But this core is slower than Mr.Beuchat et.al.

About Author

https://www.linkedin.com/in/homerhsing/