Efficiency improvements for package de.upb.crypto.math.pairings.BarretoNaehrig

[rheitjoh]

(This issue has been imported from the Gitlab repository because it seems to not have been addressed yet)

Original Text (Issue 85)

Several optimizations are pending:

1. Currently, fields are derived fromde.upb.crypto.math.structures.quotient.FiniteFieldExtension. This is inefficient, especially the implementation of multiplication. The BN fields shall directly implement the Field interface, including a Karatsuba based implementation of FF multiplication.
2. Only the less efficient Tate Pairing is implemented. Also Ate and optimal Ate pairing shall be implemented.
3. The final exponentiation is not optimized. It shall be based on Frobenius Endomorphism and multi exponentiation.
4. Remove artificial BN BaseField
5. Implement inversion in GT based on conjugation (unitary elements)

Comment by Peter Günther

The first item is handled in branch feature/native_bn_arithmetic and already partly merged into develop with commit https://git.cs.uni-paderborn.de/ag-bloemer/sis/-/commit/0b709fe25bf8c56b423edb5d2959d04e6f5828c9

Comment by Fabian Eidens

[at]peterg can you give us a hint for 2. such that we can look at it and implement it?

Comment by Peter Günther

This should be a good starting point.

Frederik Vercauteren. “Optimal pairings.” In: IEEE Transactions on
Information Theory 56.1 (2010), pp. 455–461.

Also diss of Michael Naehrig.

Comment by Peter Günther

To get something closer to an implementation, look at Algorithm 6.3 in

http://nbn-resolving.de/urn:nbn:de:hbz:466:2-24853
http://digital.ub.uni-paderborn.de/hsx/download/pdf/2041207?originalFilename=true

The expected speedup for a product of pairings is roughly factor 4 compared to Tate pairing, I guess.

Is it critical for you? If you really need it, I could implement it together with the Jacobean coordinates when there is a bit more time.

I would first implement Jacobean coordinates because it applies to a wider class of curves and because it should bring more speedup.

[rheitjoh]

Similarly to #91, it seems it was decided to make use of existing efficient pairing implementations and just use our own pairings for convenience and not performance..

[JanBobolz]

Seems about right.

For 1., we have had a Bachelor thesis looking at Karatsuba multiplication, but because of weird-ish design choices of the BigInteger interface, it's hard to employ properly.
I've recently committed 3.
Peter has implemented 5. at some point.

So I'd say this issue is mostly done and our current strategy with the library is to not put too much effort into optimizing the Java pairings, as you've said.