Expose ProjectivePoint value

[ycscaly]

The value of the x, y, and z coordinates of the ProjectivePoint struct is private, and it is intended that one should use .to_affine() to get a canonical representation of the point. That function, however, is extremely computationally costly in comparison to accessing the fields directly, clocking at 5.4642 µs.

I am now developing an aggregatable, batched Schnorr proof, and for e.g. the knowledge of the discrete log language .to_affine() becomes the bottleneck as we need to call it batch_size times as each statement should be put into the transcript.

I don't actually need to access the members of this struct (the coordinates) but I do need a unique representation in bytes that is computationally inexpensive (it should be a few nano seconds and not micro seconds.)

@tarcieri your thoughts on this?

[tarcieri]

I don't actually need to access the members of this struct (the coordinates) but I do need a unique representation in bytes that is computationally inexpensive

Are you expecting these strings to compare equal if their corresponding AffinePoints compare equal?

One thing to keep in mind is that projective points use a homogenous coordinate system, where many projective points (e.g. when the coordinates are multiplied by the same value) can map to the same affine point.

[ycscaly]

I don't actually need to access the members of this struct (the coordinates) but I do need a unique representation in bytes that is computationally inexpensive

Are you expecting these strings to compare equal if their corresponding AffinePoints compare equal?

One thing to keep in mind is that projective points use a homogenous coordinate system, where many projective points (e.g. when the coordinates are multiplied by the same value) can map to the same affine point.

That's a good point, but for our purposes, it does not matter. All we care about is to have a mapping between projective points and byte arrays. I'm fine with multiple projective points that map into the same affine point to be mapped to different byte arrays, so long as the .to/from_bytes of ProjectivePoint remain a bijective.

That being said, your comment makes it clear that this might not be for all use-cases, and so maybe implementing the standard From<> traits here could be a little misleading, and it'd be better to handle that in a dedicated method for which ample clarification could be added in the documentation. What do you think?

Let me know how to proceed, and I'll make the PR.

Thanks

[tarcieri]

Really exposing anything about the internals ProjectivePoint is not something I've personally considered before. It's really just an optimized form for performing arithmetic operations rather than something which is supposed to have a stable internal representation, and I very much worry that people who are unfamiliar with the specific properties of homogenous coordinate systems could use it to shoot themselves in the foot.

I guess the right place for this is probably zkcrypto/group#30 though that has generally been about exposing affine coordinates, not projective ones. Perhaps you could leave a comment about your use case there?

[randombit]

Depending on the implementation, exposing the projective point can leak information about the discrete logarithm (https://www.iacr.org/archive/eurocrypt2004/30270258/projective.pdf)

It sounds to me like a batched projective->affine conversion would solve your problem without introducing a footgun. Typically a batch conversion of any size is basically as efficient as a single, since you only have to do a single field inversion for the whole batch.

[ycscaly]

Depending on the implementation, exposing the projective point can leak information about the discrete logarithm (https://www.iacr.org/archive/eurocrypt2004/30270258/projective.pdf)

It sounds to me like a batched projective->affine conversion would solve your problem without introducing a footgun. Typically a batch conversion of any size is basically as efficient as a single, since you only have to do a single field inversion for the whole batch.

Thanks for that save. That does sound efficient. Can we do that instead @tarcieri ?

[tarcieri]

@ycscaly that sounds like the way to go, yes

[ycscaly]

@tarcieri you've raised concerns here regarding the safety of exposing and using the projective coordinate of an elliptic curve, which is the representation used for group operations, and suggested that we only use the affine representation, which is the canonic representation of the group element value.

A similar issue happens in groups like Paillier, which I implemented using crypto_bigint::DynResidue: retrieving the canonical representation (a number between 0 and N^2) requires an expensive montgomery_reduction operation. My question is whether I could use the number in Montgomery form, e.g. when serializing group elements and transmitting them to other parties.

A cryptographer colleague of mine looked at Montgomery form and suggested we can do that, since the representation is canonical. However, I thought it would be good to have your opinion here as well.

The alternative is a similar batch conversion routine, which I'm not certain whether it exists for Montgomery reductions.

Thanks

[tarcieri]

@ycscaly I similarly consider the use of Montgomery form as the internal representation of field elements something of an implementation detail which I haven't previously considered exposing

Likewise there are field implementations where we don't use Montgomery form, like P-521, where we use an unsaturated representation which is able to leverage unique properties of Mersenne/Solinas primes.

[ycscaly]

@ycscaly I similarly consider the use of Montgomery form as the internal representation of field elements something of an implementation detail which I haven't previously considered exposing

Likewise there are field implementations where we don't use Montgomery form, like P-521, where we use an unsaturated representation which is able to leverage unique properties of Mersenne/Solinas primes.

However, the Montgomery form is exposed in crypto-bigint::DynResidue. I understand the point regarding elliptic curves, but for groups over integers modulo some number, what is your thought?

[tarcieri]

We don't actually use crypto_bigint::modular::MontForm nee DynResidue in these crates yet (although I do plan on working on that in the primefield crate in the next set of breaking releases)

[ycscaly]

We don't actually use crypto_bigint::modular::MontForm nee DynResidue in these crates yet (although I do plan on working on that in the primefield crate in the next set of breaking releases)

Maybe the confusion stems from me putting this comment in the elliptic curve crate. I just wanted to continue the discussion as it is related. But this is a pure crypto-bigint question. I'm talking as a user that uses DynResidue exclusively and asks whether using MontForm in serialization of group values etc.

If it helps I can move the question to crypto_bigint

[tarcieri]

Aah, I mean, if you want to use Montgomery form as the wire format for your custom protocol, I don't see any problem with that

[ycscaly]

Aah, I mean, if you want to use Montgomery form as the wire format for your custom protocol, I don't see any problem with that

Great,thats what I wanted to know - that it doesn't open up a new attack vector vs. the alternative of sending the reduced Uint