Batch Conversion of Projective -> Affine Points

[ycscaly]

In #937 I explained how expensive the to_affine() function is in k256, and how it can become a bottleneck in certain situations. My suggestion to expose the projective coordinates got some backfire:

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

Instead, the suggestion was to have a batch conversion:

          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.

Originally posted by @randombit in #937 (comment)

I am for this, and wondering:

1. where can I find an algorithm for this method that I could implement @randombit
2. if there is a specific interface you wish for me to expose @tarcieri

[randombit]

Regarding the algorithm:

The Jacobian coordinates of an elliptic curve point (x,y) are (X,Y,Z) where x = X / Z^2 and y = Y / Z^3. To convert from projective to affine coordinates, we must compute the modular inverse of Z, which is expensive. Given Z^-1 we can cheaply compute Z^-2 and Z^-3 and so compute the affine coordinates x and y.

If we wish to convert many points at once, then we have to compute the inverse of Z_i for i \in 0..n

There is a trick for computing many modular inverses at once, often called "Montgomery's trick", which reduces the problem of computing n inverses to computing a single inversion, plus some storage and O(n) extra multiplications. There is a description of Montgomery's trick in https://iacr.org/archive/pkc2004/29470042/29470042.pdf section 2.2 that explains this part as well as I could. It is also described in Algorithm 2.26 of "Guide to Elliptic Curve Cryptography".

So the batch conversion works by applying Montgomery's trick to reduce the n inversions of the Z coordinates to just a single inversion, then using that to extract each individual inverse Z_i^-1 and computing the affine coordinates.

There is an implementation of this technique in C++ here that demonstrates how it all comes together.

[ycscaly]

Regarding the algorithm:

The Jacobian coordinates of an elliptic curve point (x,y) are (X,Y,Z) where x = X / Z^2 and y = Y / Z^3. To convert from projective to affine coordinates, we must compute the modular inverse of Z, which is expensive. Given Z^-1 we can cheaply compute Z^-2 and Z^-3 and so compute the affine coordinates x and y.

If we wish to convert many points at once, then we have to compute the inverse of Z_i for i \in 0..n

There is a trick for computing many modular inverses at once, often called "Montgomery's trick", which reduces the problem of computing n inverses to computing a single inversion, plus some storage and O(n) extra multiplications. There is a description of Montgomery's trick in https://iacr.org/archive/pkc2004/29470042/29470042.pdf section 2.2 that explains this part as well as I could. It is also described in Algorithm 2.26 of "Guide to Elliptic Curve Cryptography".

So the batch conversion works by applying Montgomery's trick to reduce the n inversions of the Z coordinates to just a single inversion, then using that to extract each individual inverse Z_i^-1 and computing the affine coordinates.

There is an implementation of this technique in C++ here that demonstrates how it all comes together.

Thanks!

[ycscaly]

@tarcieri so the Montgomery trick for efficient simultaneous inversion is generic for inversion in a prime field, (actually even for any field in which the numbers have an inverse), and is not limited to projective->affine nor to secp256k1.

Should we design a generic function that takes a sequence of elements and returns a sequence of their inverses, given an Inverse operation, or should we limit it to secp256k1 specifically?

Also, we would then need to call this from a simultaneous to_affine() functionality.

Thoughts on this, or should I do a PR with my intended design?

[tarcieri]

A generic implementation in either elliptic-curve or primeorder sounds good. Note we're about to move into a phase of breaking changes where we bump minor versions, so unless you want to wait for that it'd be good to get in ASAP.

Perhaps this is also worth discussing having a trait for in group?

[ycscaly]

Will try to get a PR for this today, max tomorrow, so it'll be in the next release

[ycscaly]

The PR for batch inversion is ready for review, I am now thinking how to do batch affine conversion: unlike Invert this relies upon internal implementation details and must be implemented differently for different elliptic curves. Two questions:

1. should I design a trait for this in elliptic-curve or have standalone functions?
2. how can I implement it in k256 if the batch inversion logic isn't available yet as a dependency? I'd need to work with the git version, and there seems to be inner dependencies needing patching etc.

[tarcieri]

A trait-based approach is great.

You can use your branch by editing this repo's toplevel Cargo.toml and adding:

[patch.crates-io]
elliptic-curve = { git = "https://github.com/ycscaly/traits", branch = "batch_invert" }

It would definitely be great to see working tests against k256 before merging RustCrypto/traits#1376

[ycscaly]

A trait-based approach is great.

You can use your branch by editing this repo's toplevel Cargo.toml and adding:

[patch.crates-io]
elliptic-curve = { git = "https://github.com/ycscaly/traits", branch = "batch_invert" }

It would definitely be great to see working tests against k256 before merging RustCrypto/traits#1376

This gives error: warning: Patch elliptic-curve v0.13.6 (https://github.com/ycscaly/traits?branch=batch_invert#e8c3ea25)` was not used in the crate graph.`

[ycscaly]

A trait-based approach is great.
You can use your branch by editing this repo's toplevel Cargo.toml and adding:

[patch.crates-io]
elliptic-curve = { git = "https://github.com/ycscaly/traits", branch = "batch_invert" }

It would definitely be great to see working tests against k256 before merging RustCrypto/traits#1376

This gives error: warning: Patch elliptic-curve v0.13.6 ([https://github.com/ycscaly/traits?branch=batch_invert#e8c3ea25)](https://github.com/ycscaly/traits?branch=batch_invert#e8c3ea25)%60) was not used in the crate graph.

@tarcieri the reason is version incompatibility. traits relies upon elliptic_curve-0.13.0-pre.5 whereas the repo is currently at 0.13.6. And there are breaking changes. I'm uncertain how to proceed with testing this, and this also prevents me from implementing ToAffineBatch in k256.

[tarcieri]

traits relies upon elliptic_curve-0.13.0-pre.5

No? https://github.com/RustCrypto/traits/blob/aa21684/elliptic-curve/Cargo.toml#L3

I think you're doing something wrong. I can push up a branch if that's helpful.

[tarcieri]

Here you go. Works for me: master...use-elliptic-curve-from-git

[ycscaly]

Here you go. Works for me: master...use-elliptic-curve-from-git

Sorry, my problem was that I was working on an out of date version of master as a base.
It indeed works, and I've created the PR.

[ycscaly]

#971 closed this

[ycscaly]

@tarcieri I stumbled of what I think is a bug (or at the least, unclear documentation). In

elliptic-curves/k256/src/arithmetic/projective.rs

Line 295 in 5d1c252

// Even a single zero value will fail inversion for the entire batch.

I have put a remark that zero-values fails batch-inversion, so I replace those values with the corresponding element in points. However, that element can also be zero, which in turn leads to a panic as the unwrap in

elliptic-curves/k256/src/arithmetic/projective.rs

Line 302 in 5d1c252

let zs_inverses = <FieldElement as BatchInvert<Z>>::batch_invert(zs).unwrap();

fails.

[tarcieri]

Yeah, that seems busted. The comment refers to using FieldElement::ONE as a placeholder, but instead it's using points[i].z.

@ycscaly can you open a new issue (or PR) for this?

[ycscaly]

Yeah, that seems busted. The comment refers to using FieldElement::ONE as a placeholder, but instead it's using points[i].z.

@ycscaly can you open a new issue (or PR) for this?

I'm really not sure what happened here. I originally wrote the code in that way so that the array was initialized to ONE and only put the points there in case it was safe, the refactor confused me a bit, and I misunderstood it yesterday, and today I re-read and it seems fine. Also there was a test that should have caught this as it put Identitity as part of the batch. I also re-run the code that should have panicked and it didn't, thought it did yesterday. Perhaps a cargo update I ran influenced this, and there was some buggy code that was patched? I'm a little uncertain how to debug this, or whether we should, further, as this seems very odd at this point. If you don't know, tomorrow I'll try to go back to a commit that was broken and re-run.

[ycscaly]

Yeah, that seems busted. The comment refers to using FieldElement::ONE as a placeholder, but instead it's using points[i].z.
@ycscaly can you open a new issue (or PR) for this?

I'm really not sure what happened here. I originally wrote the code in that way so that the array was initialized to ONE and only put the points there in case it was safe, the refactor confused me a bit, and I misunderstood it yesterday, and today I re-read and it seems fine. Also there was a test that should have caught this as it put Identitity as part of the batch. I also re-run the code that should have panicked and it didn't, thought it did yesterday. Perhaps a cargo update I ran influenced this, and there was some buggy code that was patched? I'm a little uncertain how to debug this, or whether we should, further, as this seems very odd at this point. If you don't know, tomorrow I'll try to go back to a commit that was broken and re-run.

Ok, I managed to get it to panic again (using k256 13.3 so this is not an update issue), and I think I found the root cause; invert() fails if self.normalizes_to_zero(), not if ct_eq(&FieldElement::ZERO).

@tarcieri if this is truly the problem, I wouldn't even say this is an error in batch_normalize_generic(): I believe it is very misleading for an equality method to not check if the normalized variant equals.

Is this intended? if not, it should be fixed. If it is indeed, I'll change batch_normalize_generic().

[tarcieri]

Please open a PR to fix the issue.

Re: issues with non-normalized/lazy field elements, really what would help is making separate types for normalized vs lazy field elements, like FieldElement and LazyFieldElement, which can ensure normalization is performed where needed to avoid these sorts of bugs in the first place: #531

[ycscaly]

Please open a PR to fix the issue.

Re: issues with non-normalized/lazy field elements, really what would help is making separate types for normalized vs lazy field elements, like FieldElement and LazyFieldElement, which can ensure normalization is performed where needed to avoid these sorts of bugs in the first place: #531

Done #1029