feedback about sgn0

[kwantam]

Mike Scott sent me an email with several pieces of feedback on sgn0. Let's discuss if/how to handle these in this issue, and then I'll put together a PR.

The high-level message is that the sgn0 definitions are too complex, and may lead to implementation errors. Specific suggestions:

1. Get rid of sgn0_be and only use sgn0_le.

   • Pros: only one sgn0 variant would be great.
   • Cons: this would mean that existing curves that use sgn0_be for point compression wouldn't be able to reuse that implementation for hashing. Also, it looks like the BLS12-381 community is pretty firmly entrenched at this point, which would make life hard for the BLS signatures draft.

2. If sgn0 returns 0 for positive or zero, and 1 for negative, then it (at least, sgn0_le) could be much simpler, especially for the m=1 case:

    def sgn0_le(x):
        return x mod 2
   

   This could also be made quite simple for quadratic extensions:

    def sgn0_le(x):   # x = (x_1, x_2)
        p0 = x_1 == 0
        p1 = x_1 mod 2
        p2 = x_2 mod 2
        return p1 | (p0 & p2)
   

   • Pros: simplifies specifying sgn0_le. Not clear whether it simplifies sgn0_be, but it might.
   • Cons: is (0, 1) less intuitive than (1, -1) for (positive, negative) respectively?

3. Rather than specifying field extension sgn0 in terms of vector representations, specify it in terms of towering. That is, express sgn0 for Fp2 in terms of two calls to sgn0 for Fp; sgn0 for Fp4 in terms of two calls to sgn0 for Fp2; etc.

   • Pros: may result in simpler constant-time implementations.
   • Cons: requires us to define towering at sufficient detail in the document to actually specify this approach. Is not compatible with any existing point compression technique that I'm aware of.

[kwantam]

Here's my take.

First, to address the complexity of the current spec, we could give simplified versions of sgn0_le and sgn0_be for the m=1 case, and maybe also for the m=2 case for sgn0_be.

Point-by-point for each of the above suggestions:

1. It would be nice to get rid of sgn0_be, but it will make some implementations more complex, and it will definitely make the BLS signatures standard slightly more controversial (since the only suites right now are BLS12-381, and everyone there seems to prefer to use big-endian signedness).

   So I'm not in favor of removing sgn0_be.

2. I'm fine with (0,1) instead f (1,-1). It will make the specifications simpler (because we can use logical operators rather than CMOV). It will also require a careful consistency pass through the document, but that's not so hard.

   So I'm slightly in favor of (0, 1), but could go either way.

3. The towering suggestion is clever, but I think adding all the towering notation to this document will make it strictly harder to understand, and it would require us to totally give up on the idea of matching point compression for extension fields. (I suppose if we decide to get rid of sgn0_be then we're already breaking point compression compatibility, in which case the second argument doesn't apply.)

   Also, it will probably require a whole bunch of different "towering combinators" that describe what to do for different degrees at each level of the tower (certainly we'll need degree 2 and 3, possibly others).

   So: I'm against making the towering change.

[kwantam]

@armfazh @chris-wood thoughts?

[armfazh]

it will definitely make the BLS signatures standard slightly more controversial (since the only suites right now are BLS12-381, and everyone there seems to prefer to use big-endian signedness).

The choice of sgn0 is particular to hash to curve, isn't it?. BLS signatures still can use big-endian sign for other purposes. As noted, verifying parity is easier to implement.

Moving from (1,-1) to (0,1) is equivalent to move from sgn to parity. So, sgn can be defined in terms of parity.

The proposed sgn function is too specific to the tower used. However, how it is actually computed the sgn function in the current setting?

For example, if we have an element in Fp6,
Let A \in Fp6, A = A1 x + A0. (as a quadratic extension over Fp3)
A1 \in Fp3, A1 = a2 y^2 + a1 y + a0 ( a cubic extension over Fp)

[kwantam]

The choice of sgn0 is particular to hash to curve, isn't it?. BLS signatures still can use big-endian sign for other purposes. As noted, verifying parity is easier to implement.

You're totally right, they could keep using the existing method for compression and only change sgn0 for hashing. This gives up on the hope that everyone could use the same sign method for both compression and hashing, but maybe that's OK.

Moving from (1,-1) to (0,1) is equivalent to move from sgn to parity. So, sgn can be defined in terms of parity.

True.

The proposed sgn function is too specific to the tower used. However, how it is actually computed the sgn function in the current setting?

For example, if we have an element in Fp6,
Let A \in Fp6, A = A1 x + A0. (as a quadratic extension over Fp3)
A1 \in Fp3, A1 = a2 y^2 + a1 y + a0 ( a cubic extension over Fp)

In the current version, I think we'd expect people to write down the element of Fp6 as a 6-vector over, say, the basis given by the Cartesian product {y^2, y, 1} x {x, 1} and then compute the sign using the existing method. Right?

[armfazh]

In the current version, I think we'd expect people to write down the element of Fp6 as a 6-vector over, say, the basis given by the Cartesian product {y^2, y, 1} x {x, 1} and then compute the sign using the existing method. Right?

hence, it is equivalent to what is proposed by going trough the tower, or not?
because, at the end, the sgn will be a function coefficients in the ground field.

[kwantam]

Ah, got it! (Sorry for being slow 😄)

I think you're right: it's possible, as long as the ground field elements have the "right" ordering, that the two methods would agree. This is a really good point 👍

[chris-wood]

My $0.02:

1. I'm OK removing the BE variant, given that it primarily benefits one use case.
2. I don't think (0,1) would cause much confusion. As a plus, specifying sgn0 in terms of parity does seem to simplify things.
3. I'm less comfortable with this proposal. @kwantam, does it depend on a particular basis representation for field elements?

[chris-wood]

ping @kwantam @armfazh!

[armfazh]

it seems we are all agree on points 1 and 2.
For the point 3, we might need to specify the order in which the elements and sub-elements are evaluated. So, a sgn function that does not depend on the order of element will be ideal.

[kwantam]

It's not obvious to me how to make sgn independent of the evaluation order (or that it's even possible), but it's a very cool idea...

I'm still not super jazzed about killing sgn0_be, but I'll go along with it if both of you prefer it.

(0,1) seems fine.

I should have some time in the next couple days to put together edits for points 1 and 2, and then I guess we can re-evaluate whether we definitely want to remove sgn0_be.

[kwantam]

I've opened #230 to address issues (1) and (2).

If we really want to deal with the towering issue (issue (3)), we can add an appendix about it. As @armfazh pointed out, it's possible to implement the towering approach in a way that's compatible with the vector approach as currently specified.

[bwesterb]

It is an interesting question whether there is a generalisation of the sign to an arbitrary extension field.

What do we expect?

• sgn(-x) = -sgn(x)
• sgn(T(x)) = sgn(x) for any automorphism T

Such a sgn does not exist for GF(p^2) if n:=(p-1)/2 is odd. Call an element x (strictly) positive if sgn(x)=1. GP(p^2) has two automorphisms: the trivial one and the Frobenius automorphism which sends x to x^p. There are exactly n:=(p-1)/2 positive elements fixed by the Frobenius automorphism. This leaves 2(n^2+n)-n positive elements that cannot be fixed by the automorphism/. As n is assumed to be odd, this number is odd. But that cannot be as they have to pair up via the Frobenius automorphism! Thus such sgn does not exist.

The existence of such a sign is actually equivalent to the problem of selecting a square root. Indeed, suppose there is a way we can pick a preferred square root irrespective of representation. Then we can define such a sgn function as follows. Define sgn(0) = 0. Given a non-zero element x, check whether sqrt(x^2)=x where sqrt is our preferred square root. Define sgn(x)=1 if sqrt(x^2)=x and -1 otherwise. This sgn satisfies our assumptions.

I'm now thinking about the general case for F(p^n).

[kwantam]

The existence of such a sign is actually equivalent to the problem of selecting a square root. Indeed, suppose there is a way we can pick a preferred square root irrespective of representation. Then we can define such a sgn function as follows. Define sgn(0) = 0. Given a non-zero element x, check whether sqrt(x^2)=x where sqrt is our preferred square root. Define sgn(x)=1 if sqrt(x^2)=x and -1 otherwise. This sgn satisfies our assumptions.

This is a good point! and in fact we're using this idea, but backwards, in the draft---we don't specify how to compute sqrt, and instead we always restrict sgn0 of the result...

[kwantam]

• sgn(T(x)) = sgn(x) for any automorphism T

As you say, this appears to be problematic for the general case. So we give up on this, only requiring that sgn0(x) = -sgn0(-x) for x != 0. (Or, well, the moral equivalent if sgn0 outputs {0,1}.)

[bwesterb]

I've thought a bit more about the existence of an automorphism invariant sign. It cannot exist in F(p^k) with k even and p an odd prime. Indeed, let x be an element of F(p^k) such that x^2 is a quadratic-non residue of F(p). Such a x exists because k is even and so x^(p^k-1)/2 = x^{ (p-1)/2 (1 + p + ... + p^{k-1} ) } = ( ( x^{(p-1)/2} )^k = 1.

Note (x^2)^{(p-1)/2} = -1 and so x^p = -x

Note that F(y)=y^p is an automorphism and so sign(x) = sign(x^p) = sign(-x) = -sign(x). Contradiction!

This leaves the question open for odd k≥3.