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

Faster scalar multiplication in G1. #79

Open
wants to merge 1 commit into
base: main
Choose a base branch
from

Conversation

dfaranha
Copy link

@dfaranha dfaranha commented Nov 29, 2021

Implements the GLV method for scalar multiplication in G1 in constant time.

The code includes a BETA constant (cube root of -1) to apply the GLV endomorphism, a GLV recoding algorithm to convert the scalar into subscalars and a regular recoding algorithm to compute a wNAF version with prescribed non-zero positions (due to Joye and Tunstall). The GLV and regular recoding methods are orthogonal and do not depend on each other if the former is deemed too risky.

The code probably can be simplified, but this version should start some discussion.

vihu added a commit to vihu/bls12_381 that referenced this pull request Dec 5, 2021
randombit added a commit to randombit/bls12_381 that referenced this pull request Jun 29, 2022
@ebfull
Copy link
Contributor

ebfull commented Dec 8, 2022

This needs rebasing -- which we can do if you don't have time. However, I want to point out that the BETA constant introduced in this PR already exists in the g1 module but is different from the one you introduce (it's the other non-trivial cube root of 1). We'd need to remove that constant and use the one we already have which is also called BETA in the code. But would that interfere with this algorithm?

@dfaranha
Copy link
Author

dfaranha commented Dec 8, 2022

Changing the BETA for the other cube root of 1 will change the GLV vector basis for recoding. I can try computing it over Christmas, but you're right that it needs non-trivial rebasing.

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 this pull request may close these issues.

None yet

2 participants