alt_bn128_pairing.cpp

Go to the documentation of this file.

 
#include <cassert>
#include <libff/algebra/curves/alt_bn128/alt_bn128_g1.hpp>
#include <libff/algebra/curves/alt_bn128/alt_bn128_g2.hpp>
#include <libff/algebra/curves/alt_bn128/alt_bn128_init.hpp>
#include <libff/algebra/curves/alt_bn128/alt_bn128_pairing.hpp>
#include <libff/common/profiling.hpp>
 
namespace libff
{
 
bool alt_bn128_ate_G1_precomp::operator==(
    const alt_bn128_ate_G1_precomp &other) const
{
    return (this->PX == other.PX && this->PY == other.PY);
}
 
std::ostream &operator<<(
    std::ostream &out, const alt_bn128_ate_G1_precomp &prec_P)
{
    out << prec_P.PX << OUTPUT_SEPARATOR << prec_P.PY;
 
    return out;
}
 
std::istream &operator>>(std::istream &in, alt_bn128_ate_G1_precomp &prec_P)
{
    in >> prec_P.PX;
    consume_OUTPUT_SEPARATOR(in);
    in >> prec_P.PY;
 
    return in;
}
 
bool alt_bn128_ate_ell_coeffs::operator==(
    const alt_bn128_ate_ell_coeffs &other) const
{
    return (
        this->ell_0 == other.ell_0 && this->ell_VW == other.ell_VW &&
        this->ell_VV == other.ell_VV);
}
 
std::ostream &operator<<(std::ostream &out, const alt_bn128_ate_ell_coeffs &c)
{
    out << c.ell_0 << OUTPUT_SEPARATOR << c.ell_VW << OUTPUT_SEPARATOR
        << c.ell_VV;
    return out;
}
 
std::istream &operator>>(std::istream &in, alt_bn128_ate_ell_coeffs &c)
{
    in >> c.ell_0;
    consume_OUTPUT_SEPARATOR(in);
    in >> c.ell_VW;
    consume_OUTPUT_SEPARATOR(in);
    in >> c.ell_VV;
 
    return in;
}
 
bool alt_bn128_ate_G2_precomp::operator==(
    const alt_bn128_ate_G2_precomp &other) const
{
    return (
        this->QX == other.QX && this->QY == other.QY &&
        this->coeffs == other.coeffs);
}
 
std::ostream &operator<<(
    std::ostream &out, const alt_bn128_ate_G2_precomp &prec_Q)
{
    out << prec_Q.QX << OUTPUT_SEPARATOR << prec_Q.QY << "\n";
    out << prec_Q.coeffs.size() << "\n";
    for (const alt_bn128_ate_ell_coeffs &c : prec_Q.coeffs) {
        out << c << OUTPUT_NEWLINE;
    }
    return out;
}
 
std::istream &operator>>(std::istream &in, alt_bn128_ate_G2_precomp &prec_Q)
{
    in >> prec_Q.QX;
    consume_OUTPUT_SEPARATOR(in);
    in >> prec_Q.QY;
    consume_newline(in);
 
    prec_Q.coeffs.clear();
    size_t s;
    in >> s;
 
    consume_newline(in);
 
    prec_Q.coeffs.reserve(s);
 
    for (size_t i = 0; i < s; ++i) {
        alt_bn128_ate_ell_coeffs c;
        in >> c;
        consume_OUTPUT_NEWLINE(in);
        prec_Q.coeffs.emplace_back(c);
    }
 
    return in;
}
 
/* final exponentiations */
 
alt_bn128_Fq12 alt_bn128_final_exponentiation_first_chunk(
    const alt_bn128_Fq12 &elt)
{
    enter_block("Call to alt_bn128_final_exponentiation_first_chunk");
 
    /*
      Computes result = elt^((q^6-1)*(q^2+1)).
      Follows, e.g., Beuchat et al page 9, by computing result as follows:
         elt^((q^6-1)*(q^2+1)) = (conj(elt) * elt^(-1))^(q^2+1)
      More precisely:
      A = conj(elt)
      B = elt.inverse()
      C = A * B
      D = C.Frobenius_map(2)
      result = D * C
    */
 
    const alt_bn128_Fq12 A = alt_bn128_Fq12(elt.coeffs[0], -elt.coeffs[1]);
    const alt_bn128_Fq12 B = elt.inverse();
    const alt_bn128_Fq12 C = A * B;
    const alt_bn128_Fq12 D = C.Frobenius_map(2);
    const alt_bn128_Fq12 result = D * C;
 
    leave_block("Call to alt_bn128_final_exponentiation_first_chunk");
 
    return result;
}
 
alt_bn128_Fq12 alt_bn128_exp_by_neg_z(const alt_bn128_Fq12 &elt)
{
    enter_block("Call to alt_bn128_exp_by_neg_z");
 
    alt_bn128_Fq12 result = elt.cyclotomic_exp(alt_bn128_final_exponent_z);
    if (!alt_bn128_final_exponent_is_z_neg) {
        result = result.unitary_inverse();
    }
 
    leave_block("Call to alt_bn128_exp_by_neg_z");
 
    return result;
}
 
alt_bn128_Fq12 alt_bn128_final_exponentiation_last_chunk(
    const alt_bn128_Fq12 &elt)
{
    enter_block("Call to alt_bn128_final_exponentiation_last_chunk");
 
    // clang-format off
    /*
      Follows Laura Fuentes-Castaneda et al. "Faster hashing to G2"
      by computing:
 
      result = elt^(q^3 * (12*z^3 + 6z^2 + 4z - 1) +
                    q^2 * (12*z^3 + 6z^2 + 6z) +
                    q   * (12*z^3 + 6z^2 + 4z) +
                    1   * (12*z^3 + 12z^2 + 6z + 1))
      which equals
 
      result = elt^( 2z * ( 6z^2 + 3z + 1 ) * (q^4 - q^2 + 1)/r ).
 
      Using the following addition chain:
 
      A = exp_by_neg_z(elt)  // = elt^(-z)
      B = A^2                // = elt^(-2*z)
      C = B^2                // = elt^(-4*z)
      D = C * B              // = elt^(-6*z)
      E = exp_by_neg_z(D)    // = elt^(6*z^2)
      F = E^2                // = elt^(12*z^2)
      G = epx_by_neg_z(F)    // = elt^(-12*z^3)
      H = conj(D)            // = elt^(6*z)
      I = conj(G)            // = elt^(12*z^3)
      J = I * E              // = elt^(12*z^3 + 6*z^2)
      K = J * H              // = elt^(12*z^3 + 6*z^2 + 6*z)
      L = K * B              // = elt^(12*z^3 + 6*z^2 + 4*z)
      M = K * E              // = elt^(12*z^3 + 12*z^2 + 6*z)
      N = M * elt            // = elt^(12*z^3 + 12*z^2 + 6*z + 1)
      O = L.Frobenius_map(1) // = elt^(q*(12*z^3 + 6*z^2 + 4*z))
      P = O * N              // = elt^(q*(12*z^3 + 6*z^2 + 4*z) * (12*z^3 + 12*z^2 + 6*z + 1))
      Q = K.Frobenius_map(2) // = elt^(q^2 * (12*z^3 + 6*z^2 + 6*z))
      R = Q * P              // = elt^(q^2 * (12*z^3 + 6*z^2 + 6*z) + q*(12*z^3 + 6*z^2 + 4*z) * (12*z^3 + 12*z^2 + 6*z + 1))
      S = conj(elt)          // = elt^(-1)
      T = S * L              // = elt^(12*z^3 + 6*z^2 + 4*z - 1)
      U = T.Frobenius_map(3) // = elt^(q^3(12*z^3 + 6*z^2 + 4*z - 1))
      V = U * R              // = elt^(q^3(12*z^3 + 6*z^2 + 4*z - 1) + q^2 * (12*z^3 + 6*z^2 + 6*z) + q*(12*z^3 + 6*z^2 + 4*z) * (12*z^3 + 12*z^2 + 6*z + 1))
      result = V
    */
    // clang-format on
 
    const alt_bn128_Fq12 A = alt_bn128_exp_by_neg_z(elt);
    const alt_bn128_Fq12 B = A.cyclotomic_squared();
    const alt_bn128_Fq12 C = B.cyclotomic_squared();
    const alt_bn128_Fq12 D = C * B;
    const alt_bn128_Fq12 E = alt_bn128_exp_by_neg_z(D);
    const alt_bn128_Fq12 F = E.cyclotomic_squared();
    const alt_bn128_Fq12 G = alt_bn128_exp_by_neg_z(F);
    const alt_bn128_Fq12 H = D.unitary_inverse();
    const alt_bn128_Fq12 I = G.unitary_inverse();
    const alt_bn128_Fq12 J = I * E;
    const alt_bn128_Fq12 K = J * H;
    const alt_bn128_Fq12 L = K * B;
    const alt_bn128_Fq12 M = K * E;
    const alt_bn128_Fq12 N = M * elt;
    const alt_bn128_Fq12 O = L.Frobenius_map(1);
    const alt_bn128_Fq12 P = O * N;
    const alt_bn128_Fq12 Q = K.Frobenius_map(2);
    const alt_bn128_Fq12 R = Q * P;
    const alt_bn128_Fq12 S = elt.unitary_inverse();
    const alt_bn128_Fq12 T = S * L;
    const alt_bn128_Fq12 U = T.Frobenius_map(3);
    const alt_bn128_Fq12 V = U * R;
 
    const alt_bn128_Fq12 result = V;
 
    leave_block("Call to alt_bn128_final_exponentiation_last_chunk");
 
    return result;
}
 
alt_bn128_GT alt_bn128_final_exponentiation(const alt_bn128_Fq12 &elt)
{
    enter_block("Call to alt_bn128_final_exponentiation");
    /* OLD naive version:
        alt_bn128_GT result = elt^alt_bn128_final_exponent;
    */
    alt_bn128_Fq12 A = alt_bn128_final_exponentiation_first_chunk(elt);
    alt_bn128_GT result = alt_bn128_final_exponentiation_last_chunk(A);
 
    leave_block("Call to alt_bn128_final_exponentiation");
    return result;
}
 
/* ate pairing */
 
void doubling_step_for_flipped_miller_loop(
    const alt_bn128_Fq two_inv,
    alt_bn128_G2 &current,
    alt_bn128_ate_ell_coeffs &c)
{
    const alt_bn128_Fq2 X = current.X, Y = current.Y, Z = current.Z;
 
    // A = X1 * Y1 / 2
    const alt_bn128_Fq2 A = two_inv * (X * Y);
    // B = Y1^2
    const alt_bn128_Fq2 B = Y.squared();
    // C = Z1^2
    const alt_bn128_Fq2 C = Z.squared();
    // D = 3 * C
    const alt_bn128_Fq2 D = C + C + C;
    // E = twist_b * D
    const alt_bn128_Fq2 E = alt_bn128_twist_coeff_b * D;
    // F = 3 * E
    const alt_bn128_Fq2 F = E + E + E;
    // G = (B+F)/2
    const alt_bn128_Fq2 G = two_inv * (B + F);
    // H = (Y1+Z1)^2-(B+C)
    const alt_bn128_Fq2 H = (Y + Z).squared() - (B + C);
    // I = E-B
    const alt_bn128_Fq2 I = E - B;
    // J = X1^2
    const alt_bn128_Fq2 J = X.squared();
    // E_squared = E^2
    const alt_bn128_Fq2 E_squared = E.squared();
 
    // X3 = A * (B-F)
    current.X = A * (B - F);
    // Y3 = G^2 - 3*E^2
    current.Y = G.squared() - (E_squared + E_squared + E_squared);
    // Z3 = B * H
    current.Z = B * H;
    // ell_0 = xi * I
    c.ell_0 = alt_bn128_twist * I;
    // ell_VW = - H (later: * yP)
    c.ell_VW = -H;
    // ell_VV = 3*J (later: * xP)
    c.ell_VV = J + J + J;
}
 
void mixed_addition_step_for_flipped_miller_loop(
    const alt_bn128_G2 base, alt_bn128_G2 &current, alt_bn128_ate_ell_coeffs &c)
{
    const alt_bn128_Fq2 X1 = current.X, Y1 = current.Y, Z1 = current.Z;
    const alt_bn128_Fq2 &x2 = base.X, &y2 = base.Y;
 
    // D = X1 - X2*Z1
    const alt_bn128_Fq2 D = X1 - x2 * Z1;
    // E = Y1 - Y2*Z1
    const alt_bn128_Fq2 E = Y1 - y2 * Z1;
    // F = D^2
    const alt_bn128_Fq2 F = D.squared();
    // G = E^2
    const alt_bn128_Fq2 G = E.squared();
    // H = D*F
    const alt_bn128_Fq2 H = D * F;
    // I = X1 * F
    const alt_bn128_Fq2 I = X1 * F;
    // J = H + Z1*G - (I+I)
    const alt_bn128_Fq2 J = H + Z1 * G - (I + I);
 
    // X3 = D*J
    current.X = D * J;
    // Y3 = E*(I-J)-(H*Y1)
    current.Y = E * (I - J) - (H * Y1);
    // Z3 = Z1*H
    current.Z = Z1 * H;
    // ell_0 = xi * (E * X2 - D * Y2)
    c.ell_0 = alt_bn128_twist * (E * x2 - D * y2);
    // ell_VV = - E (later: * xP)
    c.ell_VV = -E;
    // ell_VW = D (later: * yP)
    c.ell_VW = D;
}
 
alt_bn128_ate_G1_precomp alt_bn128_ate_precompute_G1(const alt_bn128_G1 &P)
{
    enter_block("Call to alt_bn128_ate_precompute_G1");
 
    alt_bn128_G1 Pcopy = P;
    Pcopy.to_affine_coordinates();
 
    alt_bn128_ate_G1_precomp result;
    result.PX = Pcopy.X;
    result.PY = Pcopy.Y;
 
    leave_block("Call to alt_bn128_ate_precompute_G1");
    return result;
}
 
alt_bn128_ate_G2_precomp alt_bn128_ate_precompute_G2(const alt_bn128_G2 &Q)
{
    enter_block("Call to alt_bn128_ate_precompute_G2");
 
    alt_bn128_G2 Qcopy(Q);
    Qcopy.to_affine_coordinates();
 
    // could add to global params if needed
    alt_bn128_Fq two_inv = (alt_bn128_Fq("2").inverse());
 
    alt_bn128_ate_G2_precomp result;
    result.QX = Qcopy.X;
    result.QY = Qcopy.Y;
 
    alt_bn128_G2 R;
    R.X = Qcopy.X;
    R.Y = Qcopy.Y;
    R.Z = alt_bn128_Fq2::one();
 
    const bigint<alt_bn128_Fr::num_limbs> &loop_count =
        alt_bn128_ate_loop_count;
    bool found_one = false;
    alt_bn128_ate_ell_coeffs c;
 
    for (long i = loop_count.max_bits(); i >= 0; --i) {
        const bool bit = loop_count.test_bit(i);
        if (!found_one) {
            /* this skips the MSB itself */
            found_one |= bit;
            continue;
        }
 
        doubling_step_for_flipped_miller_loop(two_inv, R, c);
        result.coeffs.push_back(c);
 
        if (bit) {
            mixed_addition_step_for_flipped_miller_loop(Qcopy, R, c);
            result.coeffs.push_back(c);
        }
    }
 
    alt_bn128_G2 Q1 = Qcopy.mul_by_q();
    assert(Q1.Z == alt_bn128_Fq2::one());
    alt_bn128_G2 Q2 = Q1.mul_by_q();
    assert(Q2.Z == alt_bn128_Fq2::one());
 
    if (alt_bn128_ate_is_loop_count_neg) {
        R.Y = -R.Y;
    }
    Q2.Y = -Q2.Y;
 
    mixed_addition_step_for_flipped_miller_loop(Q1, R, c);
    result.coeffs.push_back(c);
 
    mixed_addition_step_for_flipped_miller_loop(Q2, R, c);
    result.coeffs.push_back(c);
 
    leave_block("Call to alt_bn128_ate_precompute_G2");
    return result;
}
 
alt_bn128_Fq12 alt_bn128_ate_miller_loop(
    const alt_bn128_ate_G1_precomp &prec_P,
    const alt_bn128_ate_G2_precomp &prec_Q)
{
    enter_block("Call to alt_bn128_ate_miller_loop");
 
    alt_bn128_Fq12 f = alt_bn128_Fq12::one();
 
    bool found_one = false;
    size_t idx = 0;
 
    const bigint<alt_bn128_Fr::num_limbs> &loop_count =
        alt_bn128_ate_loop_count;
    alt_bn128_ate_ell_coeffs c;
 
    for (long i = loop_count.max_bits(); i >= 0; --i) {
        const bool bit = loop_count.test_bit(i);
        if (!found_one) {
            /* this skips the MSB itself */
            found_one |= bit;
            continue;
        }
 
        /* code below gets executed for all bits (EXCEPT the MSB itself) of
           alt_bn128_param_p (skipping leading zeros) in MSB to LSB
           order */
 
        c = prec_Q.coeffs[idx++];
        f = f.squared();
        f = f.mul_by_024(c.ell_0, prec_P.PY * c.ell_VW, prec_P.PX * c.ell_VV);
 
        if (bit) {
            c = prec_Q.coeffs[idx++];
            f = f.mul_by_024(
                c.ell_0, prec_P.PY * c.ell_VW, prec_P.PX * c.ell_VV);
        }
    }
 
    if (alt_bn128_ate_is_loop_count_neg) {
        f = f.inverse();
    }
 
    c = prec_Q.coeffs[idx++];
    f = f.mul_by_024(c.ell_0, prec_P.PY * c.ell_VW, prec_P.PX * c.ell_VV);
 
    c = prec_Q.coeffs[idx++];
    f = f.mul_by_024(c.ell_0, prec_P.PY * c.ell_VW, prec_P.PX * c.ell_VV);
 
    leave_block("Call to alt_bn128_ate_miller_loop");
    return f;
}
 
alt_bn128_Fq12 alt_bn128_ate_double_miller_loop(
    const alt_bn128_ate_G1_precomp &prec_P1,
    const alt_bn128_ate_G2_precomp &prec_Q1,
    const alt_bn128_ate_G1_precomp &prec_P2,
    const alt_bn128_ate_G2_precomp &prec_Q2)
{
    enter_block("Call to alt_bn128_ate_double_miller_loop");
 
    alt_bn128_Fq12 f = alt_bn128_Fq12::one();
 
    bool found_one = false;
    size_t idx = 0;
 
    const bigint<alt_bn128_Fr::num_limbs> &loop_count =
        alt_bn128_ate_loop_count;
    for (long i = loop_count.max_bits(); i >= 0; --i) {
        const bool bit = loop_count.test_bit(i);
        if (!found_one) {
            /* this skips the MSB itself */
            found_one |= bit;
            continue;
        }
 
        /* code below gets executed for all bits (EXCEPT the MSB itself) of
           alt_bn128_param_p (skipping leading zeros) in MSB to LSB
           order */
 
        alt_bn128_ate_ell_coeffs c1 = prec_Q1.coeffs[idx];
        alt_bn128_ate_ell_coeffs c2 = prec_Q2.coeffs[idx];
        ++idx;
 
        f = f.squared();
 
        f = f.mul_by_024(
            c1.ell_0, prec_P1.PY * c1.ell_VW, prec_P1.PX * c1.ell_VV);
        f = f.mul_by_024(
            c2.ell_0, prec_P2.PY * c2.ell_VW, prec_P2.PX * c2.ell_VV);
 
        if (bit) {
            alt_bn128_ate_ell_coeffs c1 = prec_Q1.coeffs[idx];
            alt_bn128_ate_ell_coeffs c2 = prec_Q2.coeffs[idx];
            ++idx;
 
            f = f.mul_by_024(
                c1.ell_0, prec_P1.PY * c1.ell_VW, prec_P1.PX * c1.ell_VV);
            f = f.mul_by_024(
                c2.ell_0, prec_P2.PY * c2.ell_VW, prec_P2.PX * c2.ell_VV);
        }
    }
 
    if (alt_bn128_ate_is_loop_count_neg) {
        f = f.inverse();
    }
 
    alt_bn128_ate_ell_coeffs c1 = prec_Q1.coeffs[idx];
    alt_bn128_ate_ell_coeffs c2 = prec_Q2.coeffs[idx];
    ++idx;
    f = f.mul_by_024(c1.ell_0, prec_P1.PY * c1.ell_VW, prec_P1.PX * c1.ell_VV);
    f = f.mul_by_024(c2.ell_0, prec_P2.PY * c2.ell_VW, prec_P2.PX * c2.ell_VV);
 
    c1 = prec_Q1.coeffs[idx];
    c2 = prec_Q2.coeffs[idx];
    ++idx;
    f = f.mul_by_024(c1.ell_0, prec_P1.PY * c1.ell_VW, prec_P1.PX * c1.ell_VV);
    f = f.mul_by_024(c2.ell_0, prec_P2.PY * c2.ell_VW, prec_P2.PX * c2.ell_VV);
 
    leave_block("Call to alt_bn128_ate_double_miller_loop");
 
    return f;
}
 
alt_bn128_Fq12 alt_bn128_ate_pairing(
    const alt_bn128_G1 &P, const alt_bn128_G2 &Q)
{
    enter_block("Call to alt_bn128_ate_pairing");
    alt_bn128_ate_G1_precomp prec_P = alt_bn128_ate_precompute_G1(P);
    alt_bn128_ate_G2_precomp prec_Q = alt_bn128_ate_precompute_G2(Q);
    alt_bn128_Fq12 result = alt_bn128_ate_miller_loop(prec_P, prec_Q);
    leave_block("Call to alt_bn128_ate_pairing");
    return result;
}
 
alt_bn128_GT alt_bn128_ate_reduced_pairing(
    const alt_bn128_G1 &P, const alt_bn128_G2 &Q)
{
    enter_block("Call to alt_bn128_ate_reduced_pairing");
    const alt_bn128_Fq12 f = alt_bn128_ate_pairing(P, Q);
    const alt_bn128_GT result = alt_bn128_final_exponentiation(f);
    leave_block("Call to alt_bn128_ate_reduced_pairing");
    return result;
}
 
/* choice of pairing */
 
alt_bn128_G1_precomp alt_bn128_precompute_G1(const alt_bn128_G1 &P)
{
    return alt_bn128_ate_precompute_G1(P);
}
 
alt_bn128_G2_precomp alt_bn128_precompute_G2(const alt_bn128_G2 &Q)
{
    return alt_bn128_ate_precompute_G2(Q);
}
 
alt_bn128_Fq12 alt_bn128_miller_loop(
    const alt_bn128_G1_precomp &prec_P, const alt_bn128_G2_precomp &prec_Q)
{
    return alt_bn128_ate_miller_loop(prec_P, prec_Q);
}
 
alt_bn128_Fq12 alt_bn128_double_miller_loop(
    const alt_bn128_G1_precomp &prec_P1,
    const alt_bn128_G2_precomp &prec_Q1,
    const alt_bn128_G1_precomp &prec_P2,
    const alt_bn128_G2_precomp &prec_Q2)
{
    return alt_bn128_ate_double_miller_loop(prec_P1, prec_Q1, prec_P2, prec_Q2);
}
 
alt_bn128_Fq12 alt_bn128_pairing(const alt_bn128_G1 &P, const alt_bn128_G2 &Q)
{
    return alt_bn128_ate_pairing(P, Q);
}
 
alt_bn128_GT alt_bn128_reduced_pairing(
    const alt_bn128_G1 &P, const alt_bn128_G2 &Q)
{
    return alt_bn128_ate_reduced_pairing(P, Q);
}
} // namespace libff