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.

Sign up for GitHub

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

Jump to bottom

In-circuit implementation of GLV. #250

Open
SupremoUGH opened this issue Sep 9, 2022 · 0 comments
Open

In-circuit implementation of GLV. #250

SupremoUGH opened this issue Sep 9, 2022 · 0 comments
Assignees
@SupremoUGH
Labels
A-cryptography Area: Issues and PRs related to Cryptography A-performance Area: Performance-related Issues and PRs C-enhancement Category: An issue proposing an enhancement or a PR with one P-low Priority: Low

Comments

@SupremoUGH
Copy link
Contributor

It seems that GLV (with no windowing) outperforms windowed multiplication (with window of size 2) by twice as many savings in terms of R1CS. The tricky part about implementing GLV in circuit is the first step, i.e., the scalar decomposition k -> (k1, k2) because it is performed on the ring of integers and not on Fr. The solution could be to create a struct SignedInteger in the same fashion as UnSignedInteger in eclair::num and implement the relevant traits.

The mathematical analysis of GLV vs Windowed multiplication:
https://www.notion.so/mantanetwork/Scalar-multiplication-of-elliptic-curves-194a4e70a4f943a7acbab549d4331a4d
@SupremoUGH SupremoUGH self-assigned this Sep 9, 2022
@SupremoUGH SupremoUGH added A-cryptography Area: Issues and PRs related to Cryptography A-performance Area: Performance-related Issues and PRs C-enhancement Category: An issue proposing an enhancement or a PR with one labels Sep 9, 2022
@bhgomes bhgomes added the P-low Priority: Low label Sep 9, 2022
@bhgomes bhgomes added this to the v1.1.0 milestone Sep 9, 2022
@bhgomes bhgomes removed this from the v1.1.0 milestone Feb 7, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@SupremoUGH SupremoUGH

Labels
A-cryptography Area: Issues and PRs related to Cryptography A-performance Area: Performance-related Issues and PRs C-enhancement Category: An issue proposing an enhancement or a PR with one P-low Priority: Low
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@bhgomes @SupremoUGH