Sorry for resuscitating an old thread, but I’m not finding much about the pasta curves and I would be highly interested in having some pasta curves support in the EVM. We also use them in Mina protocol and supporting them on the EVM would allow us to have a fully verified light client for Mina running in Ethereum.
2 Likes
There is a solitidy implementation here with benchmark info. GitHub - zhenfeizhang/pasta-solidity: A Solidity implementation of Halo2's Pasta curves
3 Likes
That is exactly what our Mina to Ethereum bridge is about, https://blog.nil.foundation/2021/09/30/mina-ethereum-bridge.html, GitHub - NilFoundation/mina-state-proof: In-EVM Mina State Verification. No trusted setup.
1 Like
Yes:
- BN254 is estimated to have at most 103-bit security against STNFS. If this isn’t already within reach of well-funded adversaries, such as intelligence agencies, it will be. (See this talk for why attacks on discrete-log cryptosystems require only a single large precomputation to then break any given discrete logarithm quickly; this does apply to the target group of a pairing.) I don’t think it’s a good idea to essentially force designers into trade-offs that make their protocols potentially breakable by an intelligence agency.
- While BN254’s scalar field has 2-adicity 28, Grumpkin’s scalar field has no 2-adicity, making it inefficient to perform FFTs for proof systems instantiated on Grumpkin.
Note that what Genya-Z and Pratyush have said about the relative security of the Pasta curves and pairing-friendly curves is correct. BN, BLS, and as far as I’m aware all other pairing-friendly curves used in cryptography, are constructed by CM. Pairing-friendly curves also have low embedding degrees. I’m skeptical of the value for security analysis of looking at “how structured” a construction is, but if we are going to do that then we should at least get things in the right order. At risk of oversimplifying, the ordering goes like this from least to most “structured”:
(general elliptic curves) < (CM curves like secp256k1) < (2-adic cycles like Pasta) <<< (half-pairing 2-adic cycles like Pluto-Eris) < (non-cyclic pairings) < (MNT pairing cycles) << (discrete log in \mathbb{F}_p)
All of the curves on the left of the “<<<” have high embedding degree. (A half-pairing cycle has high embedding degree for one of the curves in the cycle.) It is high embedding degree that prevents a curve from being subject to reductions that allow index calculus attacks. To my knowledge, the only attack that depends on CM structure is a slight speed up to Pollard rho in some cases. As we said in a footnote to the Halo paper:
A conservative estimate of the available improvement to Pollard rho is that on a group of prime order q with an automorphism group of order 6, the attack cost is \sqrt{\frac{\pi q}{12}}, as compared to \sqrt{\frac{\pi q}{4}} using only the negation map as described in [6]. That is, the maximum speed-up is only a factor of \sqrt{3} ≈ 1.732 for a given success probability.
(This footnote applies to j = 0 curves like secp256k1 or Pallas/Vesta, and also to BN or BLS12 pairing-friendly curves when Pollard rho is used.)
I’m obviously somewhat biased because I constructed the Pasta cycle and my colleague Sean Bowe constructed BLS12-381, but in my opinion there is a strong engineering and security justification for adding both of these as precompiles, and there’s no need to pit them against each other as is done in this thread.
4 Likes
Late to the party, but one cool application of BLS (and more generally pairing-based curves) that I don’t think pasta curves support is identity-based encryption such as timelock encryption.