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

Support mapping to all Weierstrass curves (Shallue-van de Woestijne method) #815

Open
slumber opened this issue Mar 29, 2024 · 1 comment

Comments

@slumber
Copy link
Contributor

slumber commented Mar 29, 2024

Only a handful of arkworks SW curves implement mapping, following https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-09 it's done for bls curves.

Suggestions:

  1. Introduce non-simplified SWU from here. There're existing implementations in Rust, and sage script for finding constants. Add a note for users

For curves supported by the Simplified SWU method (Section 6.6.2), that mapping is the recommended one. Otherwise, the Simplified SWU method for AB == 0 (Section 6.6.3) is recommended if the goal is best performance, while the Shallue-van de Woestijne method (Section 6.6.1) is recommended if the goal is simplicity of implementation. (The reason for this distinction is that the Simplified SWU method for AB == 0 requires implementing an isogeny map in addition to the mapping function, while the Shallue-van de Woestijne method does not.)The Shallue-van de Woestijne method (Section 6.6.1) works with any curve, and may be used in cases where a generic mapping is required. Note, however, that this mapping is almost always more computationally expensive than the curve-specific recommendations above.

  1. Implement new trait for curves like BN254, ideally for all available curves. For example, the smallest degree of isogeny with ab != 0 for BN254 is 59, which should be super inefficient.
  2. Implement simplified SWU for the pasta cycle, as the isogeny for it exists https://github.com/zcash/pasta_curves/blob/main/src/hashtocurve.rs

Problems:

  1. Name clash of SWU with currently available (simplified) SWU. Other projects call non-simplified version SVDW. Alternatively, SWU can be renamed to SSWU. This is less favorable because existing code will seamlessly start using computationally expensive version.
  2. Having different mappings doesn't favor usage of generics, i.e. users will not be able to replace one curve with another, say bn254 with bls12-381 because of different algorithms. I believe users should choose "default" mapping themselves with adding their own trait and implementing it on used curves. Related Remove SWUMap and WBMap, fix MapToCurve semantics #629
@slumber
Copy link
Contributor Author

slumber commented Mar 29, 2024

@Pratyush @mmagician @weikengchen

In case you agree with the issue I can submit PRs with implementations

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