Pairing cryptography in Rust

Pairing cryptography is an exciting area of research, and an essential component of Zcash’s zkSNARKs — proofs that transactions are valid without requiring users to reveal private information. Earlier this year we also used zkSNARKs to make Bitcoin’s first zero-knowledge contingent payment!

One of our goals going forward is to better explain how these tools work, and to make them more accessible to the public. As a first step, we’re starting development of a pairing cryptography library for Rust called “bn”. Pairing cryptography is important for zkSNARKs, but what exactly is it?

Elliptic Curves

Regular elliptic curve constructions like secp256k1 — used in Bitcoin — are designed for things like digital signatures. The points on the curve form a cyclic group: they can be added together and multiplied by scalars. It is believed to be infeasible to find the multiplicand given a point and the product point, called the “elliptic curve discrete logarithm problem”.

This asymmetry (the ease of multiplying but the difficulty of the reverse) is used to make a number of useful tools and protocols. Diffie-Hellman key exchange is a simple example: Alice multiplies Bob’s public key by her (scalar) private key, and vice versa, to find a shared secret in the presence of an eavesdropper.

This key exchange protocol can be extended to three parties, but requires two rounds: for parties A, B, and C, A obtains the shared secret by having B send his public key to C, who multiplies it by her private key and sends the result to A, who can then derive the shared secret by multiplying it by her private key.

Pairing cryptography

Pairing cryptography is an extension of these concepts. Now imagine that we have two cyclic groups: :math:`G_{1}` and :math:`G_{2}`, written additively, and a mapping to a third cyclic group of the form e: :math:`G_{1} times G_{2} rightarrow G_{T}`, where :math:`G_{T}` is written multiplicatively. If this mapping is bilinear, then:

:math:`e(a g_{1}, b g_{2}) = e(g_{1}, g_{2})^{ab}` where :math:`a` and :math:`b` are scalars and :math:`g_{1}` and :math:`g_{2}` are generators for their respective groups.

Essentially, a scalar multiplication of one of the first two group elements is equivalent to an exponentiation of the final group element.

Joux’s key agreement protocol

Let’s apply pairing cryptography to the three-party key exchange scenario above. Using pairings, we can perform the exchange in one round. Each party :math:`P` publishes their public key :math:`P^{pk} = (P^{sk} g_{1}, P^{sk} g_{2})` and keeps their private key :math:`P^{sk}` secret. All of the parties :math:`A, B, C` can compute the same shared secret using the bilinear pairing function:

Or, if you prefer code, check out an example from our new library:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

// Generate public keys in G1 and G2
let (alice_pk1, alice_pk2) = (G1::one() * &alice_sk, G2::one() * &alice_sk);
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);

// Each party computes the shared secret
let alice_ss = pairing(&bob_pk1, &carol_pk2) ^ &alice_sk;
let bob_ss = pairing(&carol_pk1, &alice_pk2) ^ &bob_sk;
let carol_ss = pairing(&alice_pk1, &bob_pk2) ^ &carol_sk;

assert!(alice_ss == bob_ss && bob_ss == carol_ss);

bn

The “bn” crate is a Rust language library for performing these pairing operations using a cryptographic construction designed by our scientists in [BCGTV14]. It uses a Barreto-Naehrig elliptic curve tuned for use in zkSNARKs. The library is new and incomplete and shouldn’t be used in production software, but it is a nice step forward in our goal of making this new kind of cryptography more widely understood and easier to use.

Check out the bn crate on github or on crates.io! And feel free to join our Slack or sign up for email notifications from our team!