Implement serialization / deserialization of Gt

[Wassasin]

For G1Affine and G2Affine we have the to_uncompressed and from_uncompressed methods. I would like to serialize Gt as well.

I'll start work on a PR.

[burdges]

Gt elements are not elliptic curve points but elements of GF(p^12) aka Fp12.

There are to_bytes and from_bytes for GF(p) aka Fp at https://github.com/zkcrypto/bls12_381/blob/master/src/fp.rs#L165-L215 so similar methods could easily be added to Fp2, Fp6, and Fp12, making these elements naively 576 bytes, but..

You must verify the Gt element lies in the correct subgroup too. Assuming the term embedding degree is not used in two different way by cryptographers, then k=12 should be the minimal k such that q divides the order of p^k-1. Any field of characteristic p has at most one subgroup of order q so it suffices to check that raising the element to the power q aka scalar::MODULOUS gives the identity.

You'd implement this check in Fp12 where this power would be implemented with square and multiply. Just fyi, this crate makes the choice to use additive notation in Gt. I think this choice is less bad than representing the additive elliptic curve operations in G1 and G2 multiplicatively, which some cryptographers have historically done to make elliptic curve operations look like operations in a Schnorr subgroup of a prime field. I'd personally prefer if operations were always reflected the underlying mathematical object myself, but whatever. ;)

There are some papers about actually compressing this representation and presumably speeding up this check, like https://eprint.iacr.org/2004/032.pdf

[Wassasin]

Also to @ebfull. I would love to get this merged and a version of this crate pushed to crates.io.

[ebfull]

@Wassasin Just published 0.1. I want to see some kind of consensus on how these should be serialized before we publish an implementation.

[Wassasin]

Meanwhile I have forked this crate into one of my crates as I am no longer able to wait on the release of this feature. I understand your reluctance but I have practical considerations that I need to address within short order.

It might be possible to create my MR branch as a separate crate, but the current bls12_381 API does not expose all the required properties to other crates to facilitate this.

[BoOTheFurious]

Is there any chance that this issue will be fixed ?
I'm using a cipher scheme based on pairing and thus ciphertext lives in Gt. So I really need the possibility of serialize/deserialize on Gt element

[mariusfrinken]

I am also working on a bilinear Elgamal cipher that uses this crate and would love to hear some good news about the serialization of Gt elements. I don't see why you don't merge the uncompressed variants from the PR above, that would give us at least something to work with. Currently, there is no possibility to persistently store & retrieve Gt elements apart from forking this repo...

[auroreguillevic]

About GT membership testing.
For the BLS12-381 curve, one has GCD(p+1-t, p^4-p^2+1) = r where p is the characteristic and t is the trace, t = u+1, r = u^4-u^2+1 and p = r * (u-1)^2 /3 + u, r and p are prime numbers.

1. Check that z in GF(p^12) satisfies z^(p^4-p^2+1) = 1 with the test z^(p^4+1) =? z^(p^2) (costs two Frobenius and a multiplication)
2. If the first test is True, then check if z^(p+1-t) = 1 with the test z^p =? z^(t-1) (costs one Frobenius and an exponentiation to t-1 = u)

For the second test, the optimized squaring formulas of Granger-Scott ePrint 2009/565, PKC'2010 can be used, or Karabina compressed squarings MathComp 82(281) p.555-579

This appears in ePrint 2021/1029 Sect. 5. More on G1, G2 and GT membership testing in Mike Scott's preprint ePrint 2021/1130 and other nice tricks for BLS curves in Section 3 of ePrint 2021/1359, joint paper with @yelhousni

[jstuczyn]

Hi! I was wondering if there's any chance of this issue being addresses in the near future? It would have been extremely useful

[mratsim]

If you implement Fp12 serialization, it would be nice to do so on the using the canonical sextic representation, instead of one that depends on the tower chosen: supranational/blst#101 (comment)

i.e. c₀ + c₁ z + c₂ z² + c₃ z³ + c₄ z⁴ + c₅ z⁵ with cᵢ being Fp₂ elements

[ebfull]

It looks like the broader effort to standardize the serialization of BLS12-381 stopped short of specifying how Gt would be serialized, at least as far as I can tell, which is not what I was expecting years ago when this issue first propped up. I was hoping multiple people (not me!) could either write a standard or at least come to a well-considered plan. This comment of mine which was thumbed-down by multiple people predicted that there would be a question of what order the coefficients should be in based on the tower, a dispute that did play out in another project and then which @mratsim points out a neat solution to in this thread years later. I didn't want to just hurriedly merge in the first serialization format that anyone could fathom and potentially preclude a superior standard.

Anyway, here's a suggestion for how to serialize Gt elements which may or may not conform with other projects.

Compressed serialization

Here we would use the technique from this paper to compress the Fp12 elements (in Gt) into Fp6 elements. Then, we'd encode the resulting Fp2 coefficients in big endian order (highest degree coefficients first, like Fp2 is serialized). (As an aside, I'm worried that the implementation Supranational folks landed on placed the coefficients in ascending order, which would mean their serialization has a mixture of ascending (Fp12) and descending (Fp2) coefficients, which is goofy.)

Uncompressed serialization

Since we have to serialize Fp6 elements anyway for the compressed serialization, which forces us in the mindset of a 2 -> 6 -> 12 tower, I see no point in caring much about making the representation canonical after all. We'll just serialize Fp12 elements as the highest degree Fp6 coefficient and then the lowest degree Fp6 coefficient.

If anyone has thoughts on this suggestion it would be helpful. I would also prefer to use a serialization that is common in the community rather than thinking up my own like I have here, but if the current state of things is that everyone rolled their own serialization different from each other, then it doesn't matter ultimately.

[ebfull]

There's another potential serialization question that I had considered a few years ago but forgot to mention, and it's another reason why I was hesitant to go ahead with a format myself without more deliberation. In some old standards document I remember reading they prescribe a serialization format for extension fields where an element a_0 + a_1 u + a_2 u^2 + ... over F_p^d is encoded as a_0 + a_1 p + a_2 p^2 + ... as a single (bigendian) integer. The coefficients a_i (mod p) could then be recovered since they're all smaller than p. I believe in the case of BLS12-381 this would allow the serialization of Fp12 and Fp6 elements to shave off a byte or two since p is ~8x smaller than 2^384 and so each coefficient "wastes" three bits on its own. We leverage that waste partially in point encodings for encoding the sign and stuff, but we wouldn't need to do this for Gt elements.

[daira]

IMHO: pick a serialisation used by another project (preferably a compressed one) and document it thoroughly. It doesn't much matter which one it is; the documentation is more important.

[daira]

In some old standards document I remember reading they prescribe a serialization format for extension fields where an element a_0 + a_1 u + a_2 u^2 + ... over F_p^d is encoded as a_0 + a_1 p + a_2 p^2 + ... as a single (bigendian) integer.

It was IEEE Std 1363 or one of its extensions, and I thought it was weird at the time. It potentially shaves off a byte in some corner cases but it is absolutely not worth the complexity; let's not do that.

[ebfull]

Compared to just packing the field elements together, the IEEE Std 1363 approach actually doesn't even save a single byte for us whether or not we're talking about Fp6 (saves 1 bit) or Fp12 elements (saves 3 bits but it's not enough to save a byte), so yeah I agree.