search

herumi / mcl

a portable and fast pairing-based cryptography library
BSD 3-Clause "New" or "Revised" License
452 stars 152 forks source link

performance and fewer bits curve #28

Closed huyuguang closed 5 years ago

huyuguang commented 5 years ago

In some scenario, for example, proofs of data possession, proofs of data retrievability, we do not need that safe, it's not the transaction. I just implement the paper https://hovav.net/ucsd/dist/verstore.pdf . In paper 3.3, it requires to calculate 10000 times ui^fi for a 320KB file, which ui is a group point and fi is a field number (BN128). Now it needs several seconds (one core). I hope I can improve the speed 10 times, and I am seeking a fewer bits curve. Is it possible? Could you please provide a curve which just use 80 bits or 64 bits?

herumi commented 5 years ago

I added BN160 which has less than 80-bit(about 70bit?) security curve, but the speed is about 1.5 times faster than BN254.

How to use.

#define MCL_MAX_FP_BIT_SIZE 192
#include <mcl/bn.hpp>

using namespace bn;
initPairing(mcl::BN160);
huyuguang commented 5 years ago

Very thanks, I will try it.

huyuguang commented 5 years ago

To get 10 times faster, maybe I should think about GPGPU?

herumi commented 5 years ago

I do not know an implementation of BN-curve pairing for GPGPU.

By the way, e(P, Q) = FE(ML(P, Q)) and e(P1, Q1)...e(Pn, Qn) = FE(ML(P1, Q1)... ML(Pn, Qn)) where FE = finalExp, ML = MillerLoop then #of FE can be reduced and it will be twice faster. Do you know the technique?

herumi commented 5 years ago

And if Q1 = ... = Qn then you can use precomputedG2. see https://github.com/herumi/mcl/blob/master/test/bn_test.cpp#L182-L191

huyuguang commented 5 years ago

I don't know it, I will do some dig, very thanks for this clue.