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

Prove that endoscaling never produces a scalar in the 2^32 multiplicative subgroup #152

Open
daira opened this issue Jan 27, 2021 · 0 comments

Comments

@daira
Copy link
Contributor

daira commented Jan 27, 2021

This eliminates a possible reason for imperfect zero-knowledgeness of proving, when using the endoscaling optimization.

It is possible to prove this by exhaustive search with an efficient shortest-vector algorithm in dimension 2, e.g. algorithm 3 of https://eprint.iacr.org/2020/454.pdf . We need the version with the stricter test at step 8, so that we get a shortest vector. For each possible subgroup element, if the norm of this vector is greater than the maximum possible norm corresponding to an endoscalar, then that subgroup element cannot be an endoscalar. Some back-of-the-envelope calculations of the cost of the exhaustive search seem to suggest that it could be done in less than 24 hours (per field), based on the performance of @str4d's PR to add Pornin's algorithm to curve25519-dalek: dalek-cryptography/curve25519-dalek#323

han0110 pushed a commit to han0110/halo2 that referenced this issue Apr 13, 2023
* feat: Parallelize `commit` blinder poly generator method

Solves the concerns raised in zcash#151 related to the performance of the
random poly generator inside of `commit`.

Resolves: zcash#151

* chore: add `from_evals` for Polynomial

* chore: add benches for commit_zk serial vs par

* fix: Correct thread_seeds iter size

* fix: Clippy

* chore: apply review suggestions

* fix: Inconsisten num of Scalars generated parallely

This fix from @ed255 fixes an error on the code proposal which was
rounding the num of Scalars to be generated and so, was producing
failures.

Co-authored-by: Edu <[email protected]>

* remove: legacy comments & code

---------

Co-authored-by: Edu <[email protected]>
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