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

[Loup Vaillant-David <[e-mail]>]

> Therefore, the best one can do is to hope map-to-curve never falls
> into a small subgroup. But in that case, wouldn’t it better to
> preclude small subgroup points from map-to-curve by design?

Only if precluding those points is less risky than just hoping. And by
a very wide margin, it's not. We have to choose between two risks:

1. The map-to-curve generates the identity point. The probability of
   that occurring is less than 2^-250 at each trial. Realistically, the
   probability that it occurs even *once* in the foreseeable future is
   well below 2^-128. Those numbers aren't just very low, they are
   *impossibly* low. I would stake my life and that of my entire family
   for a penny with those odds, and still sleep soundly at night.

2. The preclusion introduces a critical bug. The probability of *that*
   occurring is far from negligible. We can lower it, but we're only
   human. We make mistakes. We write bugs. Heck, I've even recently
   been made aware of a bug in a formally verified system (not telling
   more for obvious reasons).

Ironically, I would perhaps *not* stake lives on the correctness of the
present email, despite what I said above. I'm infinitely more likely to
have made a mistake here than I am to flip 128 coins and having them
all come up heads.

The correct way to minimise risks in this case is to simplify specs and
code as much as we can. Adding a check, especially one that you cannot
test in a black box context, is infinitely riskier than gambling on 2^-
128 probability being close enough to "impossible".

Thus, precluding small subgroup points by design is a bad idea. Don't.

Loup.