3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Conrado Apr 16 at 14:01
  • $\begingroup$ @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. $\endgroup$ – fgrieu Apr 16 at 15:02
  • $\begingroup$ 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? $\endgroup$ – SEJPM Apr 16 at 17:58
  • $\begingroup$ @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. $\endgroup$ – fgrieu Apr 16 at 18:26
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Apr 17 at 10:35
  • $\begingroup$ @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. $\endgroup$ – xorhash Apr 17 at 11:17
  • 1
    $\begingroup$ @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? $\endgroup$ – Conrado Apr 17 at 11:34
  • 2
    $\begingroup$ @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. $\endgroup$ – xorhash Apr 17 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.