
The files AKEn.CPP implement variations of the ake protocol descibed in 
http://eprint.iacr.org/2002/164/

This authenticated key exchange algorithm is used as a test-bed for testing 
fast implementations of tate-pairing based protocols.

AKE2.CPP contains an implementation that uses a non-supersingular curve with 
a 160-bit group order whose security depends on the difficulty of a 1024-bit 
discrete logarithm problem. The prime modulus is 512 bits. The "security 
multiplier" is 2. The curve parameters are in the file k2.ecs

AKE6.CPP contains an implementation that uses a non-supersingular curve with 
a 160-bit group order whose security depends on the difficulty of a 960-bit 
discrete logarithm problem. The prime modulus is 160 bits. The "security 
multiplier" is 6. The curve parameters are in the file mnt.ecs

AKE4.CPP contains an implementation that uses a non-supersingular curve with 
a 192-bit group order whose security depends on the difficulty of a 2048-bit 
discrete logarithm problem. The prime modulus is 512 bits. The "security 
multiplier" is 4. The curve parameters are in the file k4.ecs

AKE8.CPP contains an implementation that uses a non-supersingular curve with 
a 224-bit group order whose security depends on the difficulty of a 4096-bit 
discrete logarithm problem. The prime modulus is 512 bits. The "security 
multiplier" is 8. The curve parameters are in the file k8.ecs
                     
The implementations AKE2.CPP, AKE4.CPP and AKE8.CPP use a "twisted" curve, and 
compress the output of the pairing. See http://eprint.iacr.org/2004/032/

AKE4.CPP and AKE8.CPP uses a "tower extension field" as a simple way of moving 
from k=2 to k=4 and k=8. See ZZn4.CPP/ZZn8.CPP

By using a series of such extensions, higher and higher security levels can 
be reached. This is thought to be a nice way of scaling security for pairing-
based protocols. These implementations all depend on the same fast 512-bit 
modular multiplier.

Counting 512-bit modmuls for the Tate Pairing (without precomputation)

AKE2 - 4087
AKE4 - 11310
AKE8 - 47443

AKEW8 contains an implementation that uses a non-supersingular curve with a 
192-bit group order whose security depends on the difficulty of a 2048-bit 
discrete logarithm problem. The prime modulus is 256 bits. The "security 
multiplier" is 8. The curve parameters are in the file weng.ecs. This curve 
was constructed using a method due to Brezing & Weng. See 
http://eprint.iacr.org/2003/143/

Counting 256-bit modmuls for the Tate Pairing  (without precomputation)

AKEW8 - 33233 (but in practise slower than AKE4 for same level of security)


A bit of analysis.... (assuming that k=2^e but probably generally valid)

Let k be the security multiplier
Let p be the number of bits in the field
Let r be the number of bits in the group

Now kp and r are constants for a given level of security.

Let N=kp/2

Let x be the cost of an NxN multiplication. By this we mean the multiplication 
of a pair of polynomials of fixed size N bits. For N=1024 and k=4 and p=512 
this would be the cost of multiplying two degree 3 polynomials with 512-bit 
coefficients. Or for the same N=1024, k=8 and p=256, it is the cost of two 
degree 7 polynomials with 256-bit coefficients. Here we assume that these 
costs are roughly the same (which is more or less true - implementational 
issues will decide it. But it will be a fairly flat-topped optimal).

Let y be the cost of a pxp modular multiplication.

Then the cost of the tate pairing Tc is

Tc = r(6x+5yk/2+3y+8y) + (N-r)*(2x)

where the first term here is miller's algorithm (BKLS version/projective 
coordinates) and the second is the final exponentiation. Simplifying...

Tc = x(2N+4r) + r.y(5k/2+11)

The first term cost is "almost" a constant (see above). The second term 
definitely benefits from a smaller p.

With precomputation

Tc = x(2N+4r) + r.y.k/2

The common intuition is that p should be made as small as possible, and ideally 
p=r. However while this benefits the second term, the first term is largely 
invariant. For higher levels of security, the first term is predominant (as N 
gets much bigger than r)

Furthermore as p gets smaller and closer to r, a low hamming weight r becomes 
more difficult to acheive, which drives up the cost of Miller's algorithm and 
offsets any gains made for the second term.

Draw your own conclusions....



The files k2.ecs, k4.ecs and k9.ecs are created by the utility folklore.cpp
The file mnt.cpp is created by the mnt.cpp utility.

