3 ms·

Ristretto – A technique for constructing prime order elliptic curve groups

67 points by based2 8y ago

meesterdude 8y ago
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.
- shawnz 8y ago
  You better make sure that you personally discover the next important crypto technology then!
- dang 8y ago
  "Please don't post shallow dismissals, especially of other people's work." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- simcop2387 8y ago
  It's a generalization of a technique that was called decaf for doing it with cofactor 4 groups. It's a coffee joke.
abhv 8y ago
(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 https://eprint.iacr.org/2015/1060 So this performance knife-fight in the ellpitic curve streets may require some benchmarks to resolve.
- bascule 8y ago
  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 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.
- FiloSottile 8y ago
  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-arithmetic-with-parallel-formulas-ac12cf5015be 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.
  - floodyberry- 8y ago
    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.
FiloSottile 8y ago
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.
rublev 8y ago
Can I get this in English?

67 points by based2 8y ago

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.

shawnz 8y ago
You better make sure that you personally discover the next important crypto technology then!
dang 8y ago
"Please don't post shallow dismissals, especially of other people's work." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
simcop2387 8y ago
It's a generalization of a technique that was called decaf for doing it with cofactor 4 groups. It's a coffee joke.

abhv 8y ago

(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 https://eprint.iacr.org/2015/1060 So this performance knife-fight in the ellpitic curve streets may require some benchmarks to resolve.

bascule 8y ago
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 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.
FiloSottile 8y ago
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-arithmetic-with-parallel-formulas-ac12cf5015be 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.
- floodyberry- 8y ago
  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.

FiloSottile 8y ago

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.

rublev 8y ago

Can I get this in English?