Why does a pairing take so long?

[ghost]

https://crypto.stanford.edu/pbc/

I was under impression pairings would take roughly 30 milliseconds according to the link above.

But my test shows otherwise:

$ time cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/hello_world`
PT0.321907197S seconds for whatever you did.

real    0m0.840s
user    0m0.792s
sys 0m0.012s

My test code:

extern crate bn;
extern crate rand;
extern crate time;
use bn::{Group, Fr, G1, G2, pairing};
use time::PreciseTime;

fn main() {
    let rng = &mut rand::thread_rng();

    // Generate private keys
    let bob_sk = Fr::random(rng);
    let carol_sk = Fr::random(rng);

    // Generate public keys in G1 and G2
    let (bob_pk1, bob_pk2) = (G1::one() * bob_sk, G2::one() * bob_sk);
    let (carol_pk1, carol_pk2) = (G1::one() * carol_sk, G2::one() * carol_sk);

    // Time the pairing
    let start = PreciseTime::now();
    let alice_ss = pairing(bob_pk1, carol_pk2);
    let end = PreciseTime::now();

    println!("{} seconds for whatever you did.", start.to(end));
}

@chronusz

[ChronusZ]

https://link.springer.com/chapter/10.1007%2F978-3-642-17455-1_2 describes a BN pairing library that takes less than a millisecond. It seems strange that a BN pairing library would take 300x as fast.

[ebfull]

One of the reasons is that this particular curve is not tuned for pairing efficiency, but instead to work efficiently in the context of zk-SNARKs.

But the most important reason is just that this implementation is not that efficient.

[ebfull]

If you want to use pairings in your software and want them to be fast, I recommend using https://github.com/ebfull/pairing instead.

It's a more secure curve, tuned better, and performs well. Pairings take less than 3ms on x86_64. Its API is very stable. It doesn't use any unsafe code.

I don't see any point in using the bn library for anything anymore unless you're trying to do something with Zcash/Ethereum maybe.

[ebfull]

By the way, you're running the code with cargo run when you should be doing cargo run --release.. it would show a drastic performance improvement over the numbers you got.

[daira]

Also note that all of the benchmarks at https://crypto.stanford.edu/pbc/times.html are for curves with less than 80 bits of security. (Caveat: those timings are for a 1GHz Pentium III.) A curve equivalent in security to BLS12-381 would at least need to have 4572 in the "Dlog security (bits)" column. It's not possible to directly compare based on those benchmarks because they're on a much slower processor, but they seem slow to me even taking that into account. Maybe that page is just out of date, though.

[ghost]

We rebuilt the project with cargo build --release and the pairing time dropped to 12ms which was in line with expectations.