Serialisation additional bits

[kirk-baird]

Issue

BLS12-381 point serialisation is based on zcash. This specifies that the first 3 bits of a G1 / G2 point should be masked away. However it does not discuss the case where a field point is greater than the prime but with the correct number of bytes.

G1

Representation:

• uncompressed: (x, y)
• compressed: (x)

Here the first 3 bits of x will represent the: compression, value of y and infinity.
However the first 3 bits of y are not discussed.

G2

Representation: x = a + b * i and y = a + b * i

• uncompressed: (x_b, x_a, y_b, y_a)
• compressed: (x_b, x_a)

Here the first 3 bits of x_b will represent the: compression, value of y and infinity.
However the first 3 bits of x_a, y_b, y_a are not discussed.

Possible Solution

I suggest a solution where deserialising a point which has any element greater than the field prime is considered invalid. Otherwise, it is possible to have two different input bytes deserialising to the same point (which may lead to signature malleability depending on implementations).

This may be implied within many implementations however I believe it's worth clarifying.

Note: It is still possible to have G1.x or G2.x_b > the field prime, even masking the first 3 bits.

[kwantam]

Great point.

Ideally we'd like to specify the serialization format by referencing an existing document, since this draft doesn't seem like the right place to specify low-level details for particular curves. My personal opinion is that this is exactly the kind of thing that the pairing-friendly curves draft should standardize, but there may be another solution.

In any case, let's keep this issue open until we figure out who's going to resolve it.

[mratsim]

Frameworks that uses lazy reductions and/or lazy carries and so have redundant representations of their field elements have a canonicalization or normalization or full reduction routine to reduce the field elements to it's unique representation lesser than the field modulus. I'm not aware of any that would serialize a non-canonical representation. (Detailed write-up and references here: mratsim/constantine#15)

I agree that a bit more specification on the serialized format and also standardization of the terminology would be helpful. For example:

• import/export (GMP terminology)
• parse/serialize (libsecp256k1 terminology at the very least)
• "OS2SIGP"/"SIG2OSP" (for Octet-String to Signature in the same vein as I2OS and OS2I)

The pairing-curve draft does seem like a good place but this is also valid for any signature scheme even if not pairing-based.

AFAIK the only normative references somewhat related to IO/serialization are:

• I2OSP and OS2IP from RFC8017
• Standards for Efficient Cryptography, SEC1 which suggests DER (in Appendix C ASN.1 for Elliptic Curve Cryptography)

[kwantam]

The other normative references I'm aware of for point serialization are:

• IEEE 1363a-2004, Section 5.5.
• ANSI X9.62-1998, Section 4.2.

Also, SEC1 section 2.3 talks about point serialization.