Hashing to curves about curves HOT 9 CLOSED

To share some design choices - yeah, it's the most direct choice - our message isn't secret and it won't be horrible if some validators are malicious and craft some inputs that take a few tries. Most won't anyway, because of the honesty assumptions. But yeah, it has these downsides.

There are other methods we've looked at which wouldn't be too bad in our case - Fouque-Tibouchi for example. BLS12-377 doesn't have a good low-degree isogeny from what we've seen and so the method that's being used now for BLS12-381 won't work directly.

from curves.

This has been implemented in algebra, and there is in progress support for this in curves.

from curves.

Yes! cc @ValarDragon @kobigurk

from curves.

Hi! We have a generic implementation over Arkworks that uses "try and increment" here: https://github.com/celo-org/celo-bls-snark-rs/, that can definitely be ported. The downside is that it doesn't have a constant amount of operations and is not constant time in general.

from curves.

Are you guys using "try and increment" with the counter outside the SNARK to reduce the constraint count?

I have not dug looked into https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve in ages, but some authors had thoughts on doing hash-to-curve inside a SNARK once.

from curves.

That said, I realized now that you said that the authors did mention SNARKs! I'll try to find it. If you have a reference I'd appreciate it.

from curves.

How about this one for BLS: https://eprint.iacr.org/2019/403.pdf?

from curves.

Yeah, that one covers all the j = 0 curves that have an efficient isogeny from a j ≠ 0 curve, including Pallas and Vesta, secp256k1, etc.

What are yous' opinions on how to handle the isogenous curves?
a) a full curve implementation;
b) just enough to do addition and to compute the isogeny.

from curves.

There are other methods we've looked at which wouldn't be too bad in our case - Fouque-Tibouchi for example. BLS12-377 doesn't have a good low-degree isogeny from what we've seen and so the method that's being used now for BLS12-381 won't work directly.

BLS12-377 has a suitable 2-isogeny on G1 and a suitable 23-isogeny on G2 to implement Wahby-Boneh SSWU. You can find parameters here (G1) and here (G2).

from curves.