# Construction of secure Elliptic Curve subgroup over a much larger field

How can we construct an Elliptic Curve subgroup of cryptographic interest out of an Elliptic Curve over a much larger finite field, including the familiar $$\Bbb F_p$$ for prime $$p$$? The Discrete Logarithm Problem and related should conjecturally require $$\mathcal O(\sqrt q)$$ field operations, where $$q$$ is the subgroup's order, which must be known.

Motivation: in a signature à la Schnorr, having an analog to Schnorr (sub)groups, but with resistance to NFS and index calculus regardless of choice of $$p$$; yet still with parameter $$p$$ to slightly tune up the cost of field operations, for likely increased security against ASICs and hypothetical quantum computers usable for cryptanalysis, at a given group/signature size.

One way to fulfill that need would be a randomized generation procedure parametrized by bit sizes for $$p$$ and $$q$$ (much larger for $$p$$), yielding primes $$p$$ and $$q$$ and the equation of an Elliptic Curve group over field $$\Bbb F_p$$ having order a multiple of $$q$$, with some presumption of hardness of the DLP.

I care much more for security for a given size of $$q$$, and simplicity of implementation on the signature verifier side (where side channels are a non-issue), than on speed, and on ease of making a secure (side-channel resistant) implementation on the side with the private key.

I envision a 192 to 512-bit $$q$$ for 96 to 256-bit conjectured security (counted in field operations in $$\Bbb F_p$$), and $$p$$ several times that size (at least twice).

• Why do you need NFS / index calculus resistance? Unless you're using pairings they don't seem to be relevant. Regardless a pairing-friendly curve seems to be the best approach, since it will allow you to work with $E(\mathbb{F}_p)$ instead of $E(\mathbb{F}_{p^k})$ all the time. – Conrado Apr 16 '20 at 14:01
• @Conrado I tried to clarify. I make mention of NFS and index calculus as the reason I want an EC (sub)group, rather than just use a Schnorr (sub)group: as far as I know these algorithms are a consideration for parametrization of the later type of (sub)group only, at least for my main application (now explicit): signature à la Schnorr. – fgrieu Apr 16 '20 at 15:02
• Is there anything I'm missing here that stops you from picking a curve s.t. $q$ is a factor of the big-curve's order? – SEJPM Apr 16 '20 at 17:58
• @SEJPM: no, you are not missing anything. A curve of order $n$ about $p$ on the field $\Bbb F_p$, with $q$ a prime factor of $n$, would be just what I want, provided there is a feasible process to generate that with some control on the size of $q$ and $p$, and some presumption of security. – fgrieu Apr 16 '20 at 18:26

Hasse's theorem notes that for an elliptic curve over a finite field with $$\mathcal{Q}$$ elements (which would mean $$\mathcal{Q}=p$$ for a prime field $$\mathbb{F}_p$$) that has $$N$$ points, the following holds:

$$|N-(\mathcal{Q}+1)|\le 2 \sqrt{\mathcal{Q}}$$

For the sake of illustration, let's take $$\mathcal{Q}=p=8191$$. This gives us $$|N-(8191+1)| \le 2\sqrt{8191}$$, leading to this range of possible numbers of points (rounded): $$8011 \le N \le 8373$$. Since this gives a hard lower and upper bound on the number of points, clearly, a prime-order curve over a large field with the constraint that the order of the curve $$q$$ is significantly smaller than the field prime $$p$$ isn't possible.

Thus you need to ignore prime-order curves and instead have a large group $$\ell$$ and a significantly smaller prime subgroup given by cofactor $$h$$ on which we operate. The worst case impact of a large cofactor is limited to a speedup of a factor of $$\sqrt{h}$$ compared to the standard Pollard $$\rho$$ attack—but that focuses on the large group $$\ell$$, not the cofactor itself. With $$\ell$$ being the “cofactor” and the real main group being what normally is considered a cofactor, things seem to get hairy and unclear in their actual impact.

Even if this is an acceptable risk, Igor E. Shparlinksi and Andrew V. Sutherland, Finding Elliptic Curves With a Subgroup of Prescribed Size, 2017 gives you a very dense outline of what an algorithm could look like to find curves with a cofactor in a pre-determined range. Even then, the runtime of the algorithm is painfully slow for sufficiently large $$p$$ for $$\mathbb{F}_p$$ (assuming you're in the 2048-bit range for $$p$$), namely $$mp^{1/2+o(1)}$$ to the point that it is likely impractical.

• This reference is spot-on, if a bit on the theoretical side for a mere engineer like me. Thanks a lot for pointing that! There is a slightly updated journal paper online and open-access: Igor E. Shparlinski and Andrew V. Sutherland, Finding elliptic curves with a subgroup of prescribed size, in International Journal of Number Theory, 2017. – fgrieu Apr 17 '20 at 10:35
• @fgrieu Good find! And yeah, there's probably a chance to have a paper consisting of just someone sitting down, digesting the whole thing and making pseudocode for actually doing it. – xorhash Apr 17 '20 at 11:17
• @xorhash I don't see why a prime-order curve over a large field isn't possible. Won't there be around $2\sqrt(\mathcal{Q})/\log{\mathcal{Q}}$ primes in that Hasse bound? – Conrado Apr 17 '20 at 11:34
• @Conrado My bad, OP's question wants $q$ to be much lower than $p$, so you can find a prime-order curve over a large field, but you won't find a prime-order curve with an order significantly smaller than the field prime. Clarifying. – xorhash Apr 17 '20 at 12:04