DOCSEARCHbyAlgolia
Submit Docs

mcl pairing-based cryptography library

repository·master·Indexed 19 days ago

https://github.com/herumi/mcl

A high-performance, portable library for pairing-based cryptography supporting BN and BLS curves (including BLS12-381, BLS12-377, BN254, BN_SNARK1, BN381_1, and BN462). It is designed for use across Linux, macOS, Windows, WebAssembly, and mobile platforms, providing C and C++ APIs as well as bindings for Java, Python, Rust, and Go.

Tokens
12.8K
Snippets
45
Records
65
Agent score
67%

What's inside mcl

  1. Overview of mcl pairing-based cryptography library

    master

    mcl is a portable and fast library for pairing-based cryptography. It supports the optimal Ate pairing over BN curves and BLS curves.

    Supported Curves

    • BN curves:
      • BN254: BN curve over a 254-bit prime.
      • BN_SNARK1: BN curve over a 254-bit prime with high 2-adicity.
      • BN381_1: BN curve over a 381-bit prime.
      • BN462: BN curve over a 462-bit prime.
    • BLS curves:
      • BLS12_381
      • BLS12_377

    Breaking Changes in Version v3

    • The default mcl.{a,lib} has a maximum size of 384-bit for the definition field Fp and 256-bit for the order field Fr (MCL_FP_BIT=384, MCL_FR_BIT=256).
    • Arguments for Fp/Fr initialization functions have changed.
    • mclbn***.{a,lib} has been merged into mcl.{a,lib} and removed.

  2. What is the she library?

    master

    The she (somewhat homomorphic encryption) library is a public-key cryptography library based on pairings, specifically implementing L2 homomorphic encryption.

    L2 homomorphic encryption allows for multiple additions and exactly one multiplication on encrypted values. A key capability is the ability to compute the encrypted inner product of two integer vectors $x = (x_i)$ and $y = (y_i)$ while they remain encrypted:

    $\sum \text{Enc}(x_i) \text{Enc}(y_i) = \text{Enc}(\sum x_i y_i)$.

  3. MCL Mathematical Notation and Curve Concepts

    master

    MCL implements elliptic curve pairings. Understanding the notation is critical for using the API correctly.

    Field and Group Notation

    • Fp: Finite field of prime order p (the base field).
    • Fr: Finite field of prime order r (the scalar field).
    • Fp2, Fp6, Fp12: Field extensions of degree 2, 6, and 12 respectively.
    • G1: Cyclic subgroup of $E(Fp)$ (additive group).
    • G2: Cyclic subgroup of the twisted curve (additive group).
    • GT: Cyclic subgroup of $Fp12$ (multiplicative group).

    Pairing

    The pairing $e: G1 imes G2 o GT$ is implemented as an optimal ate pairing.

    Curve Parameters

    Supported curves include BN254, BN_SNARK1, BLS12_381, BLS12_377, and BN381_1. The specific bit sizes for $Fp$ and $Fr$ depend on the curve and the compilation macros (MCL_FP_BIT, MCL_FR_BIT) used during the library build.

  4. Core classes in mcl JNI

    master

    The mcl JNI library provides the following mathematical abstractions:

    • Fr: The finite field with characteristic $r$.
    • G1: The cyclic group instantiated as $E(F_p)[r]$ where $r = p + 1 - t$.
    • G2: The cyclic group instantiated as the inverse image of $E'(F_{p^2})[r]$.
    • GT: The cyclic group in the image of the optimal ate pairing ($e : G1 \times G2 \to GT$).

  5. Understand the GLV method for scalar multiplication

    master

    The GLV (Gallant-Lambert-Vanstone) method is used to speed up scalar multiplication by splitting a large scalar $x$ into two smaller scalars $a$ and $b$ such that $x = a + bL$.

    Parameter Splitting for BLS Curves

    The splitting parameters depend on the specific curve used:

    CurvebitLen(L)bitLen(r)bitLen(q)SH2
    BLS12-3811282551282**2552**127
    BLS12-3771272531282**2542**126

    GLV Multiplication Algorithm

    The algorithm uses a windowed approach with precomputed tables. For a 128-bit $L$, a window size of $w=4$ is typically optimal based on the function $f(w) = 2^w + (128+w-1)//w$.

    Pseudo-code implementation:

    def mul(P, x):
  assert(0 <= x < r)
  (a, b) = split(x) # x = a + b L
  # a, b < H=1<<128
  w = 4
  for i in range(1<<w):
    tbl1[i] = P * i
    tbl2[i] = mulLamba(tbl1[i])

  mask = (1<<w)-1
  Q = 0
  for i in range(128//w):
    for j in range(w):
      Q = dbl(Q)         ### AAA
    j1 = (a >> (w*i)) & mask
    j2 = (b >> (w*i)) & mask
    Q = add(Q, tbl2[j2]) # ADD1
    Q = add(Q, tbl1[j1]) # ADD2
  return Q

    Key Implementation Details:

    • Table Order: tbl2[j2] (the component related to $bL$) is added before tbl1[j1] (the component related to $a$).
    • Coordinate Systems: The performance comparison between Projective (Proj) and Jacobi coordinates shows that Jacobi is generally faster for doubling (dbl) but slower for addition (add) compared to Projective coordinates.

  6. How she Homomorphic Encryption works

    master

    she is a two-level (somewhat) homomorphic encryption library based on pairings. It allows for:

    • Polynomially many homomorphic additions and one multiplication over encrypted data.
    • Inner Product Computation: You can compute the inner product of two encrypted integer vectors. Example: $\sum_i \text{Enc}(x_i) \cdot \text{Enc}(y_i) = \text{Enc}(\sum_i x_i y_i)$.

    Ciphertext Classes

    • CipherTextG1: Ciphertexts in the G1 group.
    • CipherTextG2: Ciphertexts in the G2 group.
    • CipherTextGT: The result of multiplying a CipherTextG1 and a CipherTextG2.

    Decryption Note

    Decryption requires solving a small Discrete Logarithm Problem (DLP). The decryption timing is $O(m/s)$, where $s$ is the size of the table used to solve the DLP and $m$ is the size of the plaintext. Use init(hashSize, tryNum) to configure this.

  7. Verify the precision of divSmallX

    master

    The divSmallX operation checks the maximum difference between $x$ and the result of $(x / (y+1)) * y$. This is relevant for understanding potential precision loss or error bounds in division-based operations within the library.

    It is considered safe/accurate for $y \ge 1 \ll ((\text{sizeof(Unit)} * 8) / 2)$.

    python3 divsmallx-diff.py

  8. Zero-Knowledge Proof (ZKP) Classes

    master

    The library provides ZKP classes to verify properties of encrypted values without decrypting them.

    Supported Proof Types

    • ZkpBin: Verifies that an encrypted value $m$ is either 0 or 1.
    • ZkpEq: Verifies that two encrypted values $m_1$ and $m_2$ are equal.
    • ZkpBinEq: Verifies that $m_1 = m_2$ and that the value is either 0 or 1.

    ZKP Workflow

    1. Generation: During encryption, use encWithZkp... methods to generate both the ciphertext and the proof.
    2. Verification: Use the proof and the public key to verify the constraints.
    3. Decryption with Proof: When decrypting, you can use decWithZkp... to return both the decrypted value and a proof that the decryption was performed correctly.

  9. Optimize pairings with a fixed G2 point

    master

    If you are performing many pairings where one point (the $Q$ in $e(P, Q)$) is fixed in $G_2$, you can precompute values to speed up the MillerLoop for different $P$ points.

    Workflow:

    1. Determine the required buffer size using getUint64NumToPrecompute().
    2. Allocate a buffer of uint64_t.
    3. Precompute the fixed $Q$ point using precomputeG2(Qbuf, Q).
    4. Use precomputedMillerLoop(f, P, Qbuf) to compute the pairing for any $P \in G_1$ using the precomputed buffer.

    There are also specialized functions for combining multiple precomputed loops:

    • precomputedMillerLoop2: Computes $MillerLoop(P_1, Q_1buf) \cdot MillerLoop(P_2, Q_2buf)$.
    • precomputedMillerLoop2mixed: Computes $MillerLoop(P_1, Q_1) \cdot MillerLoop(P_2, Q_2buf)$ (where $Q_1$ is a standard $G_2$ point and $Q_2$ is precomputed).
    // C Example for fixed-point optimization
uint64_t *Qbuf = (uint64_t*)malloc(mclBn_getUint64NumToPrecompute() * sizeof(uint64_t));
mclBn_precomputeG2(Qbuf, Q); // precomputing fixed Q
mclBn_precomputedMillerLoop(f, P, Qbuf); // pairing of any P with fixed Q
free(Qbuf);

  11. Optimize decryption performance with DLP settings

    master

    Decryption in she requires solving a small Discrete Logarithm Problem (DLP). The decryption time is proportional to $m/s$, where $m$ is the plaintext and $s$ is the DLP table size.

    To manage performance and accuracy, use:

    • setRangeForDLP(s): Sets the DLP table size $s$.
    • setTryNum(tryNum): Sets the maximum value for $m/s$ to control the search effort.

  12. Build mcl on Linux and macOS using CMake

    master

    For x86-64 Linux and macOS, use the following steps:

    mkdir build
cd build
cmake ..
make

    For other platforms (including mingw), clang++ is required:

    mkdir build
cd build
cmake .. -DCMAKE_CXX_COMPILER=clang++
make

    Note for mingw: Use clang++ instead of gcc.

    mkdir build
cd build
cmake ..
make