Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add an invert_vartime method to ConstMontyForm #728

Closed
TitouanReal opened this issue Jan 8, 2025 · 3 comments · Fixed by #731
Closed

Add an invert_vartime method to ConstMontyForm #728

TitouanReal opened this issue Jan 8, 2025 · 3 comments · Fixed by #731

Comments

@TitouanReal
Copy link

Now that the inv method is constant time, it could be useful to have a vartime alternative.

This issue is a feature request for a method like this:

let x: ConstMontyForm<MOD, SAT_LIMBS> = ...
x.invert_vartime()

that computes the inverse of x in the field of cardinal MOD, constant time in regards x but vartime in regards to MOD.

tarcieri added a commit that referenced this issue Jan 9, 2025
Adds (back) support for computing modular inversions in variable-time
with respect to the value being inverted, which computes the specific
number of safegcd divsteps to perform based on the input, as opposed to
using a worst case number based on the bit length.

Closes #728
@tarcieri
Copy link
Member

tarcieri commented Jan 9, 2025

#731 adds the only implementation of invert_vartime we can support using the safegcd algorithm, which varies the number of iterations by the value being inverted.

This isn't quite what you're asking for in the description: unfortunately it's constant-time with respect to MOD, but variable time with respect to x, which is unfortunately the only combination we can support. It would be nice to be able to support the opposite, especially for things like elliptic curve field inversions where the modulus is public, but that only works for odd inputs, not even ones, and so field inversions are typically implemented using the fully constant-time version, at least for the case the input values to be inverted are expected to be potentially secret.

@TitouanReal
Copy link
Author

I wanted this in the hope of gaining some performance in elliptic curve field inversions.
Guess I'll go on the hunt for performance improvements in my implementation then. I got a 31-fold performance loss to reduce now, I better go back to work!

@tarcieri
Copy link
Member

tarcieri commented Jan 9, 2025

#634 is probably the best option for improving performance of field inversions

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants