Are !EdwardsPoint::is_small_order and EdwardsPoint::is_torsion_free equivalent?

[zacknewman]

Does !EdwardsPoint::is_small_order ⇔ EdwardsPoint::is_torsion_free? If not, does one direction hold?

[zacknewman]

Well I should have at least attempted to find a counterexample to the above dual-implication. Had I, I would have found that the dual-implication is not true. Specifically, even if an EdwardsPoint is not "small order"; that doesn't mean it's "torsion free".

I haven't been able to generate an EdwardsPoint that was "torsion free" but "small order", so I believe EdwardsPoint::is_torsion_free ⇒ !EdwardsPoint::is_small_order. The documentation for ed25519_dalek::VerifyingKey::is_weak states

Self::verify_strict denies weak keys

and is_weak is the same thing as is_small_order; so does it ever make sense to reject keys simply because they were not "torsion free"? It makes sense to reject keys for being "small order" if you want to prevent "point malleability", but I'm unsure if there's benefit from being even "stricter" by also rejecting keys that are not "torsion free".

I did spend some time generating VerifyingKeys via ed25519_dalek::SigningKey::verifying_key, and I never generated an EdwardsPoint that wasn't "torsion free". So it does seem like while is_weak only cares about "small order", it may not hurt to be even stricter and require "torsion free".

[zacknewman]

Well there is at least one counterexample to EdwardsPoint::is_torsion_free ⇒ !EdwardsPoint::is_small_order: EdwardsPoint::identity. Perhaps the above implication holds for all other EdwardsPoints or perhaps it's better to ensure both EdwardsPoint::is_torsion_free and !EdwardsPoint::is_small_order.

[zacknewman]

Well since the Curve25519 group has order 8q where q = 2^252+27742317777372353535851937790883648493; there are obviously points that are neither small-order nor in the prime-order subgroup. Furthermore, as one of the maintainers explains in their blog:

This means that in addition to the prime-order subgroup, Curve25519 also contains a “torsion” subgroup of small-order points. The structure of the full Curve25519 group is Z/qZ×Z/8Z, meaning that every point P in the full group can be written uniquely as the sum Q+T of a point in the prime-order subgroup (call this the prime-order component) and a point in the torsion subgroup (call this the torsion component).

From above it must be the case that, excluding the identity, Z/qZ (i.e., the prime-order subgroup) and Z/8Z (i.e., the small-order subgroup) are mutually exclusive. Thus EdwardsPoint::is_torsion_free ⇒ !EdwardsPoint::is_small_order for all EdwardsPoints excluding the identity.