`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
  • ed448-goldilocks: don't reduce points during decompression #1462
  • ed448-goldilocks: Scalar Serde implementation should match PrimeFields #1463
  • 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)
  • Don't implement PrimeGroup for EdwardsPoint and add a SubgroupPoint.
• 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
  • ed448-goldilocks: use Jacobi Symbol for FieldElement::is_square #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 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
  • ed448-goldilocks: implement BatchNormalize for DecafPoint #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
  • ed448-goldilocks: clean up benchmarks #1386
  • Implement CofactorGroup for all relevant curves #1394
  • ed448-goldilocks: merge *Scalar types and forego RFC 8032 encoding #1464
  • ed448-goldilocks: implement group traits for affine forms #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.