Admissible hash for BarretoNaehrigPointEncoding

[rheitjoh]

(This issue has been imported from the Gitlab repository because it seems to not have been addressed yet)

Original Text (Issue 212)

The BarretoNaehrigPointEncoding's hashIntoStructure currently has a todo that states:

TODO: this is not an admissible encoding in the sense of Boneh Franclin because not every element in the codomain has the same number of pre-images. E.g. by setting sel to 0, we discard 2/3 of all points. Furthermore, we can have a.e. in the sense of Boneh Franclin only if the codomain of the hash function is larger than the codomain of the encoding.

Either we should implement an admissible encoding for this or add some API for users to be made aware of potential problems when using this hash.

[rheitjoh]

So I took a look at how Mcl implements these hash functions and found the following in this file.

I don't know whether it is admissible in the sense of Boneh Franklin. Apparently the hash does cover roughly 9/16ths of points on the curve according do Fouque and Tibouchi, and it is well-distributed in the sense of Farashahi et al. (whatever that means).

Mcl

Source Code

calc is the method that does the mapping.

G_1

bool calc(G1& P, const Fp& t) const
{
    if (mapToMode_ == MCL_MAP_TO_MODE_HASH_TO_CURVE_07) {
        mapTo_WB19_.FpToG1(P, t);
        return true;
    }
    if (!mapToEc(P, t)) return false;
    mulByCofactor(P);
    return true;
}

t is the element we are hashing.

void mulByCofactor(G1& P) const
{
    switch (type_) {
    case BNtype:
        // no subgroup
        break;
    case BLS12type:
        mulByCofactorBLS12(P, P);
        break;
    }
    assert(P.isValid());
}

Don't need the cofactor multiplication for G_1 since mapToEc maps to G_1 already.

G_2

bool calc(G2& P, const Fp2& t, bool fast = false) const
{
    if (mapToMode_ == MCL_MAP_TO_MODE_HASH_TO_CURVE_07) {
        mapTo_WB19_.Fp2ToG2(P, t);
        return true;
    }
    if (!mapToEc(P, t)) return false;
    mulByCofactor(P, fast);
    return true;
}

t is the element we are hashing.

void mulByCofactor(G2& P, bool fast = false) const
{
    switch(type_) {
    case BNtype:
        mulByCofactorBN(P, P);
        break;
    case BLS12type:
        mulByCofactorBLS12(P, P, fast);
        break;
    }
    assert(P.isValid());
}

/*
    Faster Hashing to G2
    Laura Fuentes-Castaneda, Edward Knapp, Francisco Rodriguez-Henriquez
    section 6.1
    for BN
    Q = zP + Frob(3zP) + Frob^2(zP) + Frob^3(P)
        = -(18x^3 + 12x^2 + 3x + 1)cofactor_ P
*/
void mulByCofactorBN(G2& Q, const G2& P) const
{
#if 0
    G2::mulGeneric(Q, P, cofactor_);
#else
#if 0
    mpz_class t = -(1 + z_ * (3 + z_ * (12 + z_ * 18)));
    G2::mulGeneric(Q, P, t * cofactor_);
#else
    G2 T0, T1, T2;
    /*
        G2::mul (GLV method) can't be used because P is not on G2
    */
    G2::mulGeneric(T0, P, z_);
    G2::dbl(T1, T0);
    T1 += T0; // 3zP
    Frobenius(T1, T1);
    Frobenius2(T2, T0);
    T0 += T1;
    T0 += T2;
    Frobenius3(T2, P);
    G2::add(Q, T0, T2);
#endif
#endif
}

So, based on the comment above, it seems like our point, after applying the BN encoding, is not actually on G_2.
The general approach seems to be that we first map to a general point on the twisted curve, and then map to G_2 via cofactor multiplication.
"Faster Hashing to G2" provides a fast cofactor multiplication algorithm (cofactor may be quite large).
I guess applying the BN encoding does map to the right curve though, i.e. E(F_q) for G_1 and the twisted curve for G_2.

Both

bool mapToEc(G& P, const F& t) const
{
    if (mapToMode_ == MCL_MAP_TO_MODE_TRY_AND_INC) {
        naiveMapTo<G, F>(P, t);
    } else {
        if (!calcBN<G, F>(P, t)) return false;
    }
    return true;
}

/*
    P.-A. Fouque and M. Tibouchi,
    "Indifferentiable hashing to Barreto Naehrig curves,"
    in Proc. Int. Conf. Cryptol. Inform. Security Latin Amer., 2012, vol. 7533, pp.1-17.
    w = sqrt(-3) t / (1 + b + t^2)
    Remark: throw exception if t = 0, c1, -c1 and b = 2

    Maps from F^*_q to E(F_q), i.e. is a Shallue-van de Woestijne encoding.
    This only maps to the elliptic curve though, we still need to map that to G_1 / G_2?

    c1_ is set to sqrt(-3)
    c2_ is set to (-1 + sqrt(-3)) / 2
    b is the parameter for the BN curve y^2 = x^3 + b
        Why is that a boolean though here? Probably cause "throw exception if b = 2"

    Fouque et al. (Notation paragraph) define chi_q : F_q -> {-1, 0, 1}
        to be notrivial quadratic character of F^*_q extended by zero to F_q.
        Specifically, chi_q(0) = 0 and for a != 0, chi_q(a) = 1 if a is a square and -1 otherwise
*/
template<class G, class F>
bool calcBN(G& P, const F& t) const
{
    // Algorithm 1 from Fouque and Tibouchi (last section)
    F x, y, w;
    bool b;
    bool negative = legendre(&b, t) < 0; // why legendre here?
    if (!b) return false;
    if (t.isZero()) return false;
    F::sqr(w, t);
    w += G::b_;
    *w.getFp0() += Fp::one();
    if (w.isZero()) return false;
    F::inv(w, w);
    mulFp(w, c1_);
    w *= t; // finish computing w
    for (int i = 0; i < 3; i++) {
        // here we set the x_i
        switch (i) {
        case 0: F::mul(x, t, w); F::neg(x, x); *x.getFp0() += c2_; break;
        case 1: F::neg(x, x); *x.getFp0() -= Fp::one(); break;
        case 2: F::sqr(x, w); F::inv(x, x); *x.getFp0() += Fp::one(); break;
        }
        G::getWeierstrass(y, x); // y = x^3 + b, so y is the square of the y-coordinate
        // sqrt(y) is the y-coordinate of x on the curve. 
        // Functions returns 0 if success else -1. So condition only entered if cannot compute sqrt?
        if (F::squareRoot(y, y)) {
            if (negative) F::neg(y, y);
            P.set(&b, x, y, false); // This function does not only check something, it also manipulates the point
            assert(b);
            return true;
        }
    }
    return false;
}

[rheitjoh]

Regarding the admissibility: There exists a more general notion called indiffirentiability which is more general than Boneh-Franklin admissibility (e.g. see here). The encoding by P.-A. Fouque and M. Tibouchi is such an indiffentiable encoding.