Ristretto – A technique for constructing prime order elliptic curve groups | Hacker News Reader

Ristretto – A technique for constructing prime order elliptic curve groups

ristretto.group

67 pointsbased29 comments

Ristretto is the work of Henry de Valence, co-author of one of the fastest ECC implementations, curve25519-dalek, and it’s a generalization of Decaf by Mike Hamburg. It’s truly a piece of outstanding cryptography design.

Ristretto and Decaf do something awesome: they make a prime order group out of a normal curve with a cofactor. A prime order group is what many higher level constructs expect, and when that expectation breaks you hear about cofactor vulnerabilities, like the Monero double spend.

You can tiptoe around cofactors and if you do it exactly right you can survive, but that’s not the kind of safe to use and implement cryptography we’ve been trying to build recently. Ristretto solves that.

Decaf can make a prime order group from curves with cofactor 4 (that means order p*4), like Ed448. Ristretto is the generalization that works also on curves with cofactor 8 like Ed25519.

And it’s extremely fast.

(1) Interesting that this is presented as a webpage instead of a normal paper on eprint or arxiv.

(2) If Mike Hamburg is behind it (no author information is available on the page), then it has high credibility.

I would take objection to the following statement: "However, modern elliptic curve implementations with fast, simple formulas don't provide a prime-order group."

The Broker-Stevanhagen (and prior) methods can find good curves with prime order, and complete formulas for these curves that are reasonably efficient are given by Renes, Costello, and Batina in https://eprint.iacr.org/2015/1060

So this performance knife-fight in the ellpitic curve streets may require some benchmarks to resolve.

From my benchmarks (oh hi I'm the author of a multi-provider elliptic curve digital signature library for Rust), ed25519-dalek (with curve25519-dalek's AVX2 backend) seems to be winning:

https://twitter.com/bascule/status/1024313525554925568

...for both signing and verification, beating out the fiat-crypto P-256 implementation (in ring, a Rust cryptography library that wraps BoringCrypto).

libsecp256k1 seems slightly slower than fiat-crypto's P-256, even with the endomorphism optimization enabled. The Rust crate presently provide knobs for either of these things, hence the low Signatory benchmarks.

These curves predate Broker-Stevanhagen, however all of the implementations I'm comparing are production(-ish) quality.

I believe that would be an extremely quick fight. The formulas you mention are 50% slower than Edwards formulas, and on top of that they don’t parallelize: https://medium.com/@hdevalence/accelerating-edwards-curve-ar... (from the same author as Ristretto).

Re (1), AFAIK the author does not consider Ristretto finished by their extremely high (IMHO) standard.

Not to volunteer, but they can be parallelized, just not in the same manner as dalek. Even with the schnorr-style signatures (to avoid scalar inversions) and the endomorphism I still think it'd be slower, the group ops are nasty.

why would you call a technique for constructing prime order elliptic curve groups ristretto, which is itself a technique for an entirely different industry for producing less bitter espresso shots?

it's not a startup and it's not a side project. Give it a real, original name.

You better make sure that you personally discover the next important crypto technology then!

"Please don't post shallow dismissals, especially of other people's work."

https://news.ycombinator.com/newsguidelines.html

It's a generalization of a technique that was called decaf for doing it with cofactor 4 groups. It's a coffee joke.

Reply on news.ycombinator.com