`ed448-goldilocks`: Tracking Issue

[daxpedda]

This issue tracks various fixes, improvements and such for the ed448-goldilocks crate so we don't loose sight of them.

• [ ] Bugs
  • [x] #1347
  • [ ] #1336
  • [x] #1369
  • [ ] #1462
  • [ ] #1463
  • [ ] Conversions between points of different curve types should account for identity points and other exceptions. We need tests for all of those cases.
  • [ ] #1326 (I didn't look into the EdDSA code at all yet)
  • [ ] Don't implement PrimeGroup for EdwardsPoint and add a SubgroupPoint.
• [ ] Optimizations
  • [ ] #1301
  • [ ] #1303
  • [ ] #1308
  • [ ] #1309
  • [ ] #1313
  • [ ] #1314
  • [x] #1316
  • [x] #1329
  • [x] #1330
  • [x] #1332
  • [x] #1333
  • [x] #1335
  • [x] #1350
  • [x] #1461
  • [ ] Open tracking issue for implementing "Faster Complete Addition Laws for MontgomeryCurves".
  • [ ] Add de/serialization for DecafAffinePoint. Here we can add DecafAffinePoint::try_from_rng() as well and make hash2curve optional.
  • [ ] Add optimized algorithms for various arithmetic operations in affine form for all curves.
  • [ ] Add optimized conversions for affine -> projective and projective -> projective points between different curves.
  • [ ] Add optimized implementation for LinearCombination for all curves.
  • [ ] After implementing DecompressPoint for affine forms, base try_from_rng() on it.
  • [ ] Use ConstMontyForm::lincomb_vartime() where appropriate. (see https://github.com/RustCrypto/crypto-bigint/pull/904 for questions about constant-timeness)
• [ ] Additions
  • [ ] #1306
  • [x] #1334
  • [ ] #1460
  • [ ] Add a checked MontgomeryXpoint de-serialization. The current one is unchecked because that's how X448 works.
  • [ ] Add double-and-compress batching for DecafPoint.
  • [ ] Add batch conversion between points when it makes sense.
• [ ] Align with other RustCrypto curve APIs
  • [ ] Remove methods covered by traits.
  • [ ] Remove Compressed* types in favor of FieldBytes.
  • [ ] Remove (Wide)ScalarBytes typedefs.
  • [ ] Use rejection sampling for Scalar::try_from_rng() instead of modular reduction.
  • [ ] Implement missing traits on affine forms (and DecafPoint): DecompactPoint, DecompressPoint, GroupEncoding.
  • [ ] Implement serde::De/Serialize for all affine forms (and DecafPoint).
• [ ] Improvements
  • [x] #1386
  • [x] #1394
  • [ ] #1464
  • [ ] #1474
  • [ ] Move internal arithmetic methods to trait implementations.
  • [ ] Re-export internal types under more succinct names. E.g. ExtendedPoint as TwistedEdwardsPoint. Or maybe we can come up with an even better setup.
  • [ ] Rename twedwards module to twisted.
  • [ ] Rename Ed448 to Edwards448 (signature vs curve).
  • [ ] Use proptest more widely.

[tarcieri]

Refactoring suggestion: move src/curve/twedwards[.rs] => src/edwards/twisted[.rs]

[daxpedda]

Decaf448 doesn't support batch encoding in any meaningful way, as opposed to Weierstrass curves where we can use batch normalization to make encoding cheaper. However, it does support double-and-compress batching. In practice, when you want to batch encode points that are a result of scalar multiplication, you can multiply by half the scalar and then double-and-compress batch the resulting points.

So I was thinking of introducing a new trait like BatchMultiplyEncode. This trait could be implemented on Weierstrass curves as well so protocols can rely on this trait without e.g. requiring specialization or some alternative workaround.

The same applies to Ristretto255.

Will open an issue in RustCrypto/traits after we implement DecafPoint::batch_double_and_compress() and I can show off some measurements.