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

scalar mul: consider using incomplete addition/doubling #76

Closed
mratsim opened this issue Aug 24, 2020 · 1 comment
Closed

scalar mul: consider using incomplete addition/doubling #76

mratsim opened this issue Aug 24, 2020 · 1 comment
Labels
constant time ⏳ Enhancement is suitable for secret data correctness 🛂 performance 🏁 question ❓ Further information is requested

Comments

@mratsim
Copy link
Owner

mratsim commented Aug 24, 2020

In scalar multiplication we use the complete formula from

to handle the infinity point, or adding P or its opposite to itself in a constant-time fashion.

However infinity can be checked and conditionally copied at the end instead of paying that cost each doubling/addition
and my intuition is that adding P/-P to itself is not possible in a scalar multiplication context (proof?).

From the paper, the complete formula carry a 40% overhead hence we might be able to significantly increase signing speed if those assumptions hold.

@mratsim mratsim added question ❓ Further information is requested constant time ⏳ Enhancement is suitable for secret data performance 🏁 correctness 🛂 labels Aug 24, 2020
@mratsim
Copy link
Owner Author

mratsim commented Oct 4, 2020

The complete formulas are actually quite efficient (12M while Jacobian is 11M+5S) and the main overhead is the large number of addition (24A).

On G2 this can be accelerated 2x by having parallel additions, one chain using ADCX and the other using ADOX.

@mratsim mratsim closed this as completed Oct 4, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
constant time ⏳ Enhancement is suitable for secret data correctness 🛂 performance 🏁 question ❓ Further information is requested
Projects
None yet
Development

No branches or pull requests

1 participant