`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
  • ed448-goldilocks: reject identity points in Group::try_from_rng() #1347
  • Remove unnecessary checks from CompressedEdwardsY::decompress() #1336
  • ed448-goldilocks: account for oddness in Scalar divisions #1369
  • Remove torsion-check from EdwardsPoint de-serialization. These points are valid, even if not "ideal".
  • DecafPoint and EdwardsPoint de-serialization shouldn't allow invalid y-coordinates by just reducing them. This bug also introduces bias in DecafPoint::try_from_rng().
  • Conversions between points of different curve types should account for identity points and other exceptions. We need tests for all of those cases.
  • ed448_goldilocks::SigningKey::from_pkcs8_pem fails due to slice length mismatch (in 0.14.0-pre.2) #1326 (I didn't look into the EdDSA code at all yet)
• Optimizations
  • Optimize Edwards to Montgomery conversions #1301
  • Reuse Edwards windowed scalar multiplication for Decaf #1303
  • Optimize Montgomery to Edwards conversions #1308
  • Use optimized map_to_curve_elligator2_curve448() #1309
  • Add optimized Edwards addition and doubling algorithms #1313
  • Use Decaf448 specific addition algorithm #1314
  • Optimize untwisted <-> twisted Edwards conversions #1316
  • Use Extended/ExtensiblePoint more appropriately #1329
  • Make ProjectiveNielsPoint::identity() an associated constant #1330
  • Use ConstMontyForm::invert() in place of pow() #1332
  • Move function requiring AffinePoint from EdwardsPoint to AffinePoint #1333
  • Use optimized algorithm to check for Edwards torsion-freeness #1335
  • ed448-goldilocks: optimize Edwards isogeny map further #1350
  • 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.
  • 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 ConstMontyForm::lincomb_vartime() is constant-time crypto-bigint#904 for questions about constant-timeness)
• Additions
  • Curve448 with full coordinates #1306
  • ed448-goldilocks: add basic benchmark suite #1334
  • Add BatchNormalize for all curves where possible.
  • Add a checked MontgomeryXpoint de-serialization. The current one is unchecked because that's what X448 works.
  • Add double-and-compress batching for DecafPoint.
• 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
  • 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.

[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.