Python code for map2curve is incorrect

[paulmillr]

Using this code produces correct P.x, but incorrect P.y.

# add to opt_swu_g2.py
jp = map2curve_osswu2(b'abc', b'BLS12381G2_XMD:SHA-256_SSWU_RO_TESTGEN')
print(from_jacobian(jp))
# => ((1953...ea02 + 0357...6175×i), (117e...db5d + 187c...62e7×i))

See this test vector from spec:

msg     = abc
P.x     = 1953ce6d4267939c7360756d9cca8eb34aac4633ef35369a7dc249
          445069888e7d1b3f9d2e75fbd468fbcbba7110ea02
    + I * 03578447618463deb106b60e609c6f7cc446dc6035f84a72801ba1
          7c94cd800583b493b948eff0033f09086fdd7f6175
P.y     = 0882ab045b8fe4d7d557ebb59a63a35ac9f3d312581b509af0f8ea
          a2960cbc5e1e36bb969b6e22980b5cbdd0787fcf4e
    + I * 0184d26779ae9d4670aca9b267dbd4d3b30443ad05b8546d36a195
          686e1ccc3a59194aea05ed5bce7c3144a29ec047c4
u[0]    = 0a7d239c9bdb41ed2ad810820a8b4f0703f60cf5833440cd684e38
          6e235b0f092da91adbaa69562b911ebd3f820655f2
    + I * 16302b56f5a9f538c7168cd5194957903b82be6749171f8de112c8
          bd3360ca24847d0567d6e42eae0c43a7fd8530b378
u[1]    = 0a1cb4196dec71b1f704f3533cdf27f247e3ea175ddcc1ca6df0f4
          5c587eb77efc6c493848f4df98e24a32753dfcf96b
    + I * 07aac42db7f3dfbc5146c70ca0ac6157893abf4e2162e303510e0c
          efb8d024c24080b9c2a9896f6c03ffe680fc18b788

[benjaminion]

Was wrestling with this myself today as it happens...

It's because this repo doesn't yet implement the updated sgn0 function from draft 07, which is defined here.

Implementing this makes the output match the test vectors in the draft 07 spec.

Note to the maintainers: it would be really helpful to have an indication somewhere in here of which draft version the code implements. It appears to be draft 06 at the moment, but I can't find that info stated anywhere findable.

[paulmillr]

@benjaminion I implemented it in fields.py, but the output still differs. Anything wrong here?

def sgn0(x):
    sign = 0
    zero = 1
    for xi in x:
        sign_i = xi % 2
        zero_i = xi == Fq.zero
        sign = sign or (zero and sign_i)
        zero = zero and zero_i
    if not sign:
        sign = 0
    return sign

[benjaminion]

I ended up doing the following (Warnings: (a) I don't Python, (b) this breaks constant time):

In fields.py:

def sgn0(x):
    sign = 0
    zero = 1
    for x_i in x:
        sign_i = x_i % 2
        zero_i = x_i == 0
        sign = sign or (zero and sign_i)
        zero = zero and zero_i
    return sign

In opt_swu_g2.py:

            # y0 = sgn0(y0) * sgn0(t) * y0
            if sgn0(y0) != sgn0(t):
                y0 = -y0

and

            # y1 = sgn0(y1) * sgn0(t) * y1
            if sgn0(y1) != sgn0(t):
                y1 = -y1

This gets me to the answer, but there may remain other things to update. Best would be to wait until this repo is updated for draft 07. Or use py_ecc linked below.

You can check the sgn0 implementation from py_ecc

[paulmillr]

Thanks.

this breaks constant time

This ain't an issue for Python, JS, or any other GC language. GC breaks constant time, as you know. "Algorithmic" constant timeness is nice, but not too nice, and not everywhere.

[paulmillr]

@benjaminion actually py_ecc produces invalid output as well.

See: ethereum/py_ecc#98

[benjaminion]

@paulmillr

actually py_ecc produces invalid output as well.

Oh no! All I can tell you is that my Java implementation is working flawlessly against the spec test vectors 😂

[gimre-xymcity]

Due to this, there's also one more problem with opt_swu2_map:

the draft says:

Note that iso_map is a group homomorphism, meaning that point addition commutes with iso_map. Thus, when using this mapping in the hash_to_curve construction of Section 3, one can effect a small optimization by first mapping u0 and u1 to E', adding the resulting points on E', and then applying iso_map to the sum. This gives the same result while requiring only one evaluation of iso_map.

consider following two implementations

def opt_swu2_map(t, t2=None):
    Pp = osswu2_help(t)
    if t2 is not None:
        Pp2 = osswu2_help(t2)
        Pp = point_add(Pp, Pp2)

    P = iso3(Pp)
    return P # NOTE: deliberately returning without clearing cofactor

def opt_swu2_map2(t, t2=None):
    Pp = iso3(osswu2_help(t))

    if t2 is not None:
        Pp2 = iso3(osswu2_help(t2))
        Pp = point_add(Pp, Pp2)

    return Pp # NOTE: deliberately returning without clearing cofactor

both implementations should give same results, they do not.
edit, ofc with fixed sgn0 they both give same results

More importantly, this means that g2 signing test vectors in this repo are incorrect.

edit, dumb me, I now see, there's #7 waiting to be merged