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

[Mike Hamburg <[e-mail]>]

> On Apr 11, 2021, at 7:36 AM, Hao, Feng <Feng.Hao=[e-mail]> wrote:
> What this though experiment shows is an idiosyncrasy in the system. It seems the small subgroup confinement issue hasn’t been considered in CPace and OPAQUE. This is understandable given that both protocols have been assuming hash-to-curve as an idealized function. Fortunately, for the curve settings considered in the hash-to-curve draft, the size of the small subgroups is so small that the practical effect is negligible. But the effect can be dramatically different when CPace and OPAQUE are implemented in a different group where the size of the small subgroup is not small, e.g., DSA, Schnoor.

Hello Feng,

CPace and OPAQUE require prime-order groups.  Prime-order groups do not have small subgroups, other than {Id}.  CPace and OPAQUE make security assumptions on their groups, but those assumptions plausibly hold for DSA-style groups.

If you start with a uniformly random distribution on an abelian group G of order pq (where p,q are coprime) and then multiply by an appropriate factor (typically q) to get down to a subgroup H of order p, then you will have a uniformly random distribution on H.  The probability of hitting the identity in H is then 1/p, which must be negligible or else rho attacks break your scheme.  It doesn’t matter in the slightest whether q is large or small.

Or, to pull the analysis back to the full group G: the probability of landing in the small subgroup doesn’t depend on its absolute size q.  It depends on its size relative to G, which is q/(pq) = 1/p, i.e. it depends only on the size of the large group.

In sum, no, this isn’t a bigger effect for larger groups.  The only thing it really changes is the difficulty of tweaking the map before the homomorphism in order to guarantee that the identity can’t show up.  If the group is prime-order in the first place, your tweak only has to avoid one element.  But of course, if you tweak after the homomorphism, then you are only avoiding one element regardless.

Cheers,
— Mike