Construction of secure Elliptic Curve subgroup over a much larger field

Question

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).

Answer 1

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.