Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

["Hao, Feng" <[e-mail]>]

  *   hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.
Please kindly note that I explicitly refer to map_to_curve, which can return low-order points. This function is followed by clearing-the-co-factor step, but as explained this step does no help to resolve the real issue.


  *   No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.
Please See Figure 1 on p. 11 in [1]. PAK uses the result from H1 as a base generator before being raised to the power of r. The follows the same idea as SPEKE.


  *   No, it’s pretty much the exact opposite of that.

  *   DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.
Sorry, that can’t be right. if you want uniform distribution of values in Gq, the items in DDH can’t be identity elements. They should have the prime order q. Please see the explicit definition of Decision Diffie-Hellman (Problem 6.4 in Section 6.7.3) In Stinson’s book [2]. The definition in Stinson’s book makes perfect sense to me, and matches what I observe by experiments (just try toy examples yourself, and see actual distributions of values).

  *   If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.
That’s interesting. Why not integrate it into the hash-to-curve draft?

  *   No, hash_to_curve on curves with cofactor = 1 can also return the identity point, because it adds two map_to_curve results together.  That case is arguably harder, because there are very simple complete addition laws for Edwards curves with cofactor 4, but the complete addition laws for Short Weierstrass curves with cofactor 1 are more complex.
Yes, you’re right. I was thinking of the Icart’s method and SWU. But if you add two results, then it’s possible to give an identity. My point is that it’s possible to remove the identity and low-order points by design (easier if you work with co-factor =1 and a bit harder for co-factor > 1).

[1] https://eprint.iacr.org/2000/044.pdf
[2] Doug Stinson, “Cryptography: theory and practice: third edition”, 2006.