Pairing cryptography library in Rust

Related tags

Cryptography bn
Overview

bn Crates.io Build status

This is a pairing cryptography library written in pure Rust. It makes use of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide two cyclic groups G1 and G2, with an efficient bilinear pairing:

e: G1 × G2 → GT

Security warnings

This library, like other pairing cryptography libraries implementing this construction, is not resistant to side-channel attacks.

Usage

Add the bn crate to your dependencies in Cargo.toml...

[dependencies]
bn = "0.4.2"

...and add an extern crate declaration to your crate root:

extern crate bn;

API

  • Fr is an element of Fr
  • G1 is a point on the BN curve E/Fq : y^2 = x^3 + b
  • G2 is a point on the twisted BN curve E'/Fq2 : y^2 = x^3 + b/xi
  • Gt is a group element (written multiplicatively) obtained with the pairing function over G1 and G2.

Examples

Joux's key agreement protocol

In a typical Diffie-Hellman key exchange, relying on ECDLP, a three-party key exchange requires two rounds. A single round protocol is possible through the use of a bilinear pairing: given Alice's public key aP1 and Bob's public key bP2, Carol can compute the shared secret with her private key c by e(aP1, bP2)c.

(See examples/joux.rs for the full example.)

// Generate private keys
let alice_sk = Fr::random(rng);
let bob_sk = Fr::random(rng);
let carol_sk = Fr::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).pow(alice_sk);
let bob_ss = pairing(carol_pk1, alice_pk2).pow(bob_sk);
let carol_ss = pairing(alice_pk1, bob_pk2).pow(carol_sk);

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

License

Licensed under either of

at your option.

Copyright 2016 Zcash Electric Coin Company. The Zcash Company promises to maintain the "bn" crate on crates.io under this MIT/Apache-2.0 dual license.

Authors

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments
  • Speed up bigint impl

    Speed up bigint impl

    There's a lot more that could be done here, but this is a good start. Benchcmp results:

     name                         pre.bench ns/iter  post.bench ns/iter  diff ns/iter   diff %  speedup 
     fq12_exponentiation          11,716,547         10,224,742            -1,491,805  -12.73%   x 1.15 
     fq12_scalar_multiplication   37,328             32,967                    -4,361  -11.68%   x 1.13 
     fr_addition                  78                 78                             0    0.00%   x 1.00 
     fr_inverses                  39,070             38,530                      -540   -1.38%   x 1.01 
     fr_multiplication            168                139                          -29  -17.26%   x 1.21 
     fr_subtraction               94                 88                            -6   -6.38%   x 1.07 
     g1_addition                  3,793              3,273                       -520  -13.71%   x 1.16 
     g1_deserialization           1,543              1,324                       -219  -14.19%   x 1.17 
     g1_scalar_multiplication     1,061,075          923,539                 -137,536  -12.96%   x 1.15 
     g1_serialization             41,245             41,461                       216    0.52%   x 0.99 
     g1_serialization_normalized  1,557              1,550                         -7   -0.45%   x 1.00 
     g1_subtraction               3,863              3,181                       -682  -17.65%   x 1.21 
     g2_addition                  20,402             16,647                    -3,755  -18.41%   x 1.23 
     g2_deserialization           4,425,378          3,751,399               -673,979  -15.23%   x 1.18 
     g2_scalar_multiplication     5,002,151          4,310,324               -691,827  -13.83%   x 1.16 
     g2_serialization             47,679             44,978                    -2,701   -5.66%   x 1.06 
     g2_serialization_normalized  2,968              2,681                       -287   -9.67%   x 1.11 
     g2_subtraction               20,110             16,400                    -3,710  -18.45%   x 1.23 
     perform_pairing              13,292,641         11,376,729            -1,915,912  -14.41%   x 1.17 
    
    opened by Vurich 7
  • Add wnaf

    Add wnaf

    Hello!

    This is a small modification to the miller_loop and precompute methods. Both methods iterate over the bits of parameter ate_loop_count. If the bit is set to true, a line function for the G2 group element is precomputed in precompute. Then later in miller_loop, the line function is scaled by the paired G1 group element, with the result being multiplied into the accumulated Fp12 element f.

    We can take advantage of the fact that negations on an elliptic curve are essentially free, and use a Non-Adjacent-Form representation of ate_loop_count. Instead of a binary representation, each 'bit' can be either 0, 1 or -1. The hamming weight of the NAF is ~50% less than the binary form.

    The precompute algorithm is modified to iterate over NAF entries of ate_loop_count_naf. If an entry is -1, a line function relative to -G2 is computed. This reduces the number of precomputed G2 entries, from 102 to 87.

    This provides a corresponding ~15% reduction in the run-time of the miller loop, as each precompute entry requires a line doubling computation in Fp2 and a scalar multiplication in Fp12, both of which are expensive.

    opened by zac-williamson 5
  • added efficient batch pairing

    added efficient batch pairing

    Hello there!

    We've been discussing the parity bn library in the EIP-1829 telegram channel, and noticed that pairing algorithm has some noticeable areas that could be sped up.

    Specifically, the 'final exponentiation' step in a bilinear pairing only needs to be computed once for a batch of pairings. In addition, a significant portion of the 'miller loop' algorithm only needs to be performed once for a batch of pairings.

    As currently implemented, these computationally intensive steps were being performed for every pair of points passed to the library.

    I have put together a small algorithm that computes a bilinear pairing for a batch of points that takes advantage of these speedups. The resulting algorithm is at least 2x faster when computing a pairing of 10 points, which is fairly significant.

    I'm quite unfamiliar with Rust, so if there are any changes that need to be made to the PR I would be happy to make them. @shamatar from matter labs has also been hacking away at this with me, and also has a solution at https://github.com/shamatar/bn

    Cheers, Zac.

    opened by zac-williamson 5
  • The point at infinity is only representable in the jacobian at y = 1

    The point at infinity is only representable in the jacobian at y = 1

    (From upstream.) The y coordinate shouldn't be negated if it's zero.

    This doesn't break any API invariants, but it does look like you're changing the library to expose more things.

    See also https://github.com/scipr-lab/libsnark/issues/60.

    Supersedes #1

    opened by ebfull 1
  • The point at infinity is only representable in the jacobian at y = 1.

    The point at infinity is only representable in the jacobian at y = 1.

    (From upstream.) The y coordinate shouldn't be negated if it's zero.

    This doesn't break any API invariants, but it does look like you're changing the library to expose more things.

    See also https://github.com/scipr-lab/libsnark/issues/60.

    opened by ebfull 1
  • use u128 for bigint limbs

    use u128 for bigint limbs

    This PR updates the bigints (U512 and U256) to use u128 for limbs. The fields' inverses were defined over 2^64 so I had to extend them to 2^128.

    benchcmp

    name                         control ns/iter  variable ns/iter  diff ns/iter   diff %  speedup
     fq12_exponentiation          4,544,644        2,338,371           -2,206,273  -48.55%   x 1.94
     fq12_scalar_multiplication   14,569           7,125                   -7,444  -51.09%   x 2.04
     fr_addition                  17               13                          -4  -23.53%   x 1.31
     fr_inverses                  8,711            5,531                   -3,180  -36.51%   x 1.57
     fr_multiplication            104              41                         -63  -60.58%   x 2.54
     fr_subtraction               20               14                          -6  -30.00%   x 1.43
     g1_addition                  1,805            756                     -1,049  -58.12%   x 2.39
     g1_deserialization           768              482                       -286  -37.24%   x 1.59
     g1_scalar_multiplication     481,975          212,330               -269,645  -55.95%   x 2.27
     g1_serialization             9,898            6,428                   -3,470  -35.06%   x 1.54
     g1_serialization_normalized  549              431                       -118  -21.49%   x 1.27
     g1_subtraction               1,872            771                     -1,101  -58.81%   x 2.43
     g2_addition                  8,440            3,768                   -4,672  -55.36%   x 2.24
     g2_deserialization           1,776,474        864,284               -912,190  -51.35%   x 2.06
     g2_scalar_multiplication     2,056,874        983,488             -1,073,386  -52.19%   x 2.09
     g2_serialization             12,477           7,628                   -4,849  -38.86%   x 1.64
     g2_serialization_normalized  1,039            752                       -287  -27.62%   x 1.38
     g2_subtraction               8,388            3,820                   -4,568  -54.46%   x 2.20
     perform_pairing              5,315,023        2,644,591           -2,670,432  -50.24%   x 2.01
    
    opened by andresilva 0
  • Fix rustc_serialize feature non-additive

    Fix rustc_serialize feature non-additive

    @Vurich pointed out that activating rustc-serialize made the Group trait more restrictive, which could cause compilation errors. Turns out that this trait requirement isn't even required.

    opened by tomaka 0
  • Update Random Number Generators

    Update Random Number Generators

    I'm proposing to use Cryptographically Secure RNGs. I also changed the deprecated notation of try!() to ?, and put the tests in groups/mod.rs within a test module to only have rand and rand_chacha as dev-dependencies.

    opened by iquerejeta 3
Owner
Parity Technologies
Solutions for a trust-free world
Parity Technologies
Implementation of the BLS12-381 pairing-friendly elliptic curve group

bls12_381 This crate provides an implementation of the BLS12-381 pairing-friendly elliptic curve construction. This implementation has not been review

Zero-knowledge Cryptography in Rust 183 Dec 27, 2022
A pairing-based threshold cryptosystem for collaborative decryption and signatures used in HoneybadgerBFT implementation

threshold_crypto A pairing-based threshold cryptosystem for collaborative decryption and signatures. The threshold_crypto crate provides cryptographic

null 166 Dec 29, 2022
Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order).

Mundane Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order). Issues and

Google 1.1k Jan 3, 2023
Cryptography-oriented big integer library with constant-time, stack-allocated (no_std-friendly) implementations of modern formulas

RustCrypto: Cryptographic Big Integers Pure Rust implementation of a big integer library which has been designed from the ground-up for use in cryptog

Rust Crypto 88 Dec 31, 2022
Ursa - Hyperledger Ursa is a shared cryptography library

HYPERLEDGER URSA Introduction Features Libursa Libzmix Dependencies Building from source Contributing Introduction Ursa was created because people in

Hyperledger 307 Dec 20, 2022
Implementation of the Web Cryptography specification in Rust.

[wip] webcrypto Implementation of the Web Cryptography specification in Rust. This crate hopes to ease interoperability between WASM and native target

Divy Srivastava 5 Mar 7, 2022
Collect libraries and packages about cryptography in Rust.

Awesome Cryptography Rust Collect libraries and packages about cryptography in Rust. Collection Library Symmetric Public-key / Asymmetric One-way Hash

Rust Cryptography Community 282 Dec 25, 2022
A general solution for commonly used crypt in rust, collection of cryptography-related traits and algorithms.

Crypto-rs A general solution for commonly used crypt in rust, collection of cryptography-related traits and algorithms. This is a Rust implementation

houseme 4 Nov 28, 2022
Example implementation for Biscuit tokens cryptography

example implementation for Biscuit token cryptography To aid in the implementation of Biscuit tokens in various languages, this repository contains an

Clever Cloud 6 May 25, 2021
Manage secret values in-repo via public key cryptography

amber Manage secret values in-repo via public key cryptography. See the announcement blog post for more motivation. Amber provides the ability to secu

FP Complete 82 Nov 10, 2022
Cryptography-related format encoders/decoders: PKCS, PKIX

RustCrypto: Formats Cryptography-related format encoders/decoders: PKCS, PKIX. Crates Name crates.io Docs Description base64ct Constant-time encoder a

Rust Crypto 112 Dec 20, 2022
BLS12-381 cryptography using Apache Milagro

BLS12-381 Aggregate Signatures in Rust using Apache Milagro WARNING: This library is a work in progress and has not been audited. Do NOT consider the

Sigma Prime 21 Apr 4, 2022
Traits - Collection of cryptography-related traits

RustCrypto: Traits Collection of traits which describe functionality of cryptographic primitives. Crates Name Algorithm Crates.io Docs MSRV aead Authe

Rust Crypto 401 Dec 27, 2022
A down-to-the-metal ongoing cryptography challenge designed by Radical Semiconductor.

woodpecker ?? [NOTE: scoreboard will now be updated weekends, starting the weekend of 12/10/2022--sorry for delays! I'll also be merging in pull reque

Radical Semiconductor 16 Dec 15, 2022
Elliptic curve cryptography on Soroban.

Elliptic Curve Cryptography on Soroban Contract examples and reusable primitives. Groth 16 verifier. This crate provides a SorobanGroth16Verifier obje

Xycloo Labs 5 Feb 10, 2023
High-level networking library that extends the bevy_replicon library to allow snapshot interpolation and client-side prediction

bevy_replicon_snap A Snapshot Interpolation plugin for the networking solution bevy_replicon in the Bevy game engine. This library is a very rough pro

Ben 3 Oct 15, 2023
A Rust library for working with Bitcoin SV

Rust-SV A library to build Bitcoin SV applications in Rust. Documentation Features P2P protocol messages (construction and serialization) Address enco

Brenton Gunning 51 Oct 13, 2022
A Rust library for generating cryptocurrency wallets

Table of Contents 1. Overview 2. Build Guide 2.1 Install Rust 2.2a Build from Homebrew 2.2b Build from Crates.io 2.2c Build from Source Code 3. Usage

Aleo 552 Dec 29, 2022
A modern TLS library in Rust

Rustls is a modern TLS library written in Rust. It's pronounced 'rustles'. It uses ring for cryptography and libwebpki for certificate verification. S

ctz 4k Jan 9, 2023