Comments (14)
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...
from bls12_381.
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
from bls12_381.
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.
from bls12_381.
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.
- 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)
- 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
from bls12_381.
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.
from bls12_381.
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.
from bls12_381.
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
from bls12_381.
Also to @ebfull. I would love to get this merged and a version of this crate pushed to crates.io.
from bls12_381.
@Wassasin Just published 0.1
. I want to see some kind of consensus on how these should be serialized before we publish an implementation.
from bls12_381.
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.
from bls12_381.
Hi! I was wondering if there's any chance of this issue being addresses in the near future? It would have been extremely useful
from bls12_381.
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
from bls12_381.
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.
from bls12_381.
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.
from bls12_381.
Related Issues (20)
- Upgrade sha2/sha3/digest from 0.9 to 0.10 HOT 4
- Tests can't compile due to rayon MSRV update without new minor bump HOT 3
- add feat: `impl Mul<Gt> for Gt` HOT 3
- Acceptable encoding of infinite points HOT 1
- Zero point for SWJacobian HOT 1
- Bump version and republish on crates.io HOT 4
- Performance benchmarks? HOT 1
- Serde support
- Remove operations on full-group elements from the public API
- Review or recalculate w-NAF recommendations
- Interest in faster implementation of scalar multiplication in G1/G2 HOT 3
- Allow usage of MillerLoopResult independently of the builtin apis HOT 2
- How can I multiply elements in Gt with another Gt? HOT 2
- Fix `Gt::default()` implementation
- Is the latest release 0.1.1?! HOT 2
- Could you show an example to produce a key using the crate? HOT 3
- Implement algorithms for speeding up pairings HOT 1
- Missing zeroize for Gt HOT 2
- question about the code HOT 1
- Get access to the `Fp12` representation from `Gt` HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bls12_381.