ECC: Hash-to-Curve & Map-to-Curve with Constant-Time Algorithms

[qubits4all]

Implement Hash-to-Curve & Map-to-Curve Algorithms that Map to an Elliptic Curve Point in Constant-Time

Hash-to-Curve: A Hash-to-Curve algorithm hashes an arbitrary-length byte-string, and then maps this hash onto an elliptic curve point, with a guarantee that the produced point lies on the configured curve, is a member of the public generator's sub-group, and is not the point-at-infinity (identity/unit point).

Map-to-Curve: A Map-to-Curve algorithm must be reversible, and unlike Hash-to-Curve algorithms, it must also be deterministic. This latter constraint is a requirement for applications such as encryption (e.g., ElGamal encryption over elliptic curves).

• Consider hash-to-curve and map-to-curve algorithms published in the informational IETF-published paper "RFC 9380: Hashing to Elliptic Curves", by A. Faz-Hernandez, et al.

Security Requirements:

• Constant-Time (Avoiding Timing Attacks): The chosen mapping function to a point on the elliptic curve should run in constant-time, in order to mitigate potential vulnerabilities to timing attacks, which is a factor when hashing a secret/sensitive value to an elliptic curve point.
  • This requirement thereby excludes commonly-known "hunt-and-peck" algorithms, which start with a generated x-coordinate & munge it (e.g., by modifying several least significant bits) until a valid ECC point is found for the configured curve.