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

Implement FFadd and FFMul in large prime fields #1195

Open
mitschabaude opened this issue Oct 24, 2023 · 0 comments
Open

Implement FFadd and FFMul in large prime fields #1195

mitschabaude opened this issue Oct 24, 2023 · 0 comments

Comments

@mitschabaude
Copy link
Member

mitschabaude commented Oct 24, 2023

Application: RSA, zk-email, zk JWTs

Note: This is similar to #1142 and #1180, but those issues will be done for foreign fields up to 259 bits. For RSA, we need much bigger fields with sizes of 2048 bits or similar.

For small fields, there are targeted FFadd and FFmul custom gates which do addition or multiplication in a single gate (1-2 rows) plus a few range checks on outputs.

However, for large fields we don't have such specific custom gates. This issue is about implementing big-field arithmetic without additional custom gates, only using available primitives.

Primitives that could be useful:

@mitschabaude mitschabaude changed the title Implement provable RSA Implement FFadd and FFMul in large prime fields Oct 24, 2023
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

No branches or pull requests

1 participant