elliptic-curve: CofactorGroup requirement for hash2curve implementation

[andrewwhitehead]

I was looking at implementing the hash2curve traits for bls12-381 (which has an implementation, but not using these traits currently), but ran into an issue with the CofactorGroup requirement on the GroupDigest trait:

pub trait GroupDigest: ProjectiveArithmetic
where
    ProjectivePoint<Self>: CofactorGroup,
{
    /// The field element representation for a group value with multiple elements
    type FieldElement: FromOkm + MapToCurve<Output = ProjectivePoint<Self>> + Default + Copy;
...

It would make sense for the outputs of MapToCurve to be other than a ProjectivePoint<Self> because they still needs clear_cofactor to be performed, but that's not how the requirement is used here. The output is converted into the CofactorGroup only to be converted back, and prior to that the implementation must not use arithmetic operations on the points as they may not be well defined.

It is also burdensome to implement CofactorGroup if it isn't used elsewhere, because that requires all of the related group operations to be defined: Group + GroupEncoding + GroupOps<Self::Subgroup> + GroupOpsOwned<Self::Subgroup>.

For ease of implementation and to avoid representing a non-subgroup point as a ProjectivePoint<Self> I think it might be best to extend the MapToCurve trait as follows. The add_and_clear_cofactor method can be optimized when addition is well-defined for Self::CurvePoint:

pub trait MapToCurve {
    /// The intermediate representation
    type CurvePoint;
    /// The output point
    type SubGroupPoint: group::Group;

    /// Map a field element into a point
    fn map_to_curve(&self) -> Self::CurvePoint;
    
    /// Sends the result of `map_to_curve` to the curve subgroup.
    fn clear_cofactor(point: &Self::CurvePoint) -> Self::SubGroupPoint;
    
    /// Combine two `map_to_curve` outputs into a curve subgroup point.
    fn add_and_clear_cofactor(lhs: &Self::CurvePoint, rhs: &Self::CurvePoint) -> Self::SubGroupPoint {
        Self::clear_cofactor(lhs) + Self::clear_cofactor(rhs)
    }
}

[andrewwhitehead]

Additionally it seems possible that a crate might want to implement MapToCurve for multiple curves using the same FieldElement as a basis, which isn't possible at the moment. I think MapToCurve could instead be implemented for the curve itself:

pub trait MapToCurve: ProjectiveArithmetic {
    /// The intermediate representation
    type CurvePoint;
    /// The field element representation for a group value with multiple elements
    type FieldElement: FromOkm + Default + Copy;

    /// Map a field element into a point
    fn map_to_curve(element: &Self::FieldElement) -> Self::CurvePoint;

    /// Sends the result of `map_to_curve` to the curve subgroup.
    fn clear_cofactor(point: &Self::CurvePoint) -> ProjectivePoint<Self>;
    
    /// Combine two `map_to_curve` outputs into a curve subgroup point.
    fn add_and_clear_cofactor(lhs: &Self::CurvePoint, rhs: &Self::CurvePoint) -> ProjectivePoint<Self> {
        Self::clear_cofactor(lhs) + Self::clear_cofactor(rhs)
    }
}

[tarcieri]

cc @daxpedda

[daxpedda]

The proposed changes seem reasonable to me. My use-case was very limited, so I didn't have any of these problems and I also don't have any experience using hash2curve on anything else then P-256 and for OPRF and OPAQUE.

I'm happy to review any PR's, I will also contribute an OPRF crate to RustCrypto when I find time (soonish) so we can make sure compatibility remains.