Score:5

Pairing-friendly curve whose group order is a safe prime

yt flag

Are there any pairing-friendly curves whose group order is a safe prime?

That is: the order of the group is $2q + 1$ for some prime number $q$.

Or, is it impossible to have such groups?

mehdi mahdavi oliaiy avatar
ro flag
I think that you will find some curves if you search in standards or articles. You can see https://eprint.iacr.org/2005/133.pdf . If you will not find it, You can generate this by varying the curve parameters in fixed $Z_p$ then check if the number of its point that equals $\#E=2q+1$ that $q$ is a prime number.
Score:3
cn flag

None that I know of, but you might be able to construct one. (Why you'd want one however is another question...)

Generalities

You can find a somewhat related question and excellent answer here, although it's not specifically about elliptic curves. The TL;DR is basically that it's easier to build a bilinear map on groups of composite order $N=pq$ with $p$ and $q$ primes, since these will have two sub-groups of large prime order naturally from Lagrange's theorem.

Now, for Elliptic Curves things are slightly different. We are building an "elliptic curve group" that is defined over a given field. The "coordinates" of the elliptic curve points are "living" in that field, but the points themselves are "living" in the EC group.

Both have different orders. The field has its own order and the elliptic curve group has its own order $n$ (which can be composite or prime). When we talk about prime order curves, we typically consider the order of the elliptic curve group, not that of the base field over which it's defined.

The MOV attack and the embedding degree

One thing that is important to know in that field is that there is the so-called MOV attack that uses a bilinear pairing mapping two points in an elliptic curve $E(\mathbb{F}_q)$ to an element in the field $\mathbb{F}_{q^k}$, for $k$ the embedding degree of that curve. We define $k$ as being the lowest value such that $n | q^k-1$. The MOV attack is dangerous because if $k$ is small, then solving the DLP in that extension field is easier than in the initial elliptic curve group and maps back to the solution on the elliptic curve, effectively breaking its security.

So typical Elliptic Curves as we use for ECDSA, ECDH and other elliptic curve based schemes (that aren't pairing-based) have a requirement that their embedding degree is large. SEC 1 v2 says for instance:

Finally, although no general subexponential algorithms to solve the ECDLP are known, three classes of curves are susceptible to special-purpose algorithms. Firstly, elliptic curves $E$ over $F_q$ with $n$ dividing $q^B −1$ for small $B$ are susceptible to the attacks described by Menezes, Okamoto,and Vanstone [MOV93], and Frey and Rück [FR94]. The attacks efficiently reduce the ECDLP on these curves to the traditional discrete logarithm problem in a small degree extension of $F_q$. A bound $B ≥20$ was updated to $B ≥100$ in [X9.62a] to provide a large margin for safety.

Here their $B$ is our value $k$.

Why does the embedding degree matter

The choice of that embedding degree $k$ for pairing-based cryptography is a trade-off between security and efficiency: a larger embedding degree means the discrete logarithm problem is harder to solve in the resulting multiplicative group, but it also means that the operations are performed in a higher-degree extension field, which is less efficient...

Now, when we talk about "pairing-friendly" curves, what is usually meant is that we know a way to construct a pairing that will be "easily" computed for that elliptic curve. It also means we typically are expecting to have a relatively "low" value for $k$, most of the time $k \leq 24$. (If you want to have an overview of elliptic curve of embedding degree 1, I recommend you to read this 2016 paper.)

What does it mean about the security of the DLP? Let $G$ be a subgroup of order $q$ in $E(F_p)$. The Pollard-Rho algorithm on the subgroup $G$ of our elliptic curve will take $\sqrt{\frac{πq}{2}}$ steps, and each step takes ~$O(\log^2(p))$. This means that we want to make sure our subgroup order $q$ is as large as possible to make the Pollard-Rho algorithm take as long as possible.

With the above mentioned MOV attack, let $e : G\times G' →F_{p^k}$ , where $k$ is the embedding degree, the DLP on $G$ can then be translated into the DLP on $F_{p^k}$ and Pollard-Rho on our extension field $F_{p^k}$ needs also $\sqrt{\frac{πq}{2}}$ steps, but each step takes only $O(k \log(p))$, this is a huge difference in complexity.

This is why we want to have large embedding degree $k$ for elliptic curves used for usual ECC, as I mentioned above already, but not necessarily in pairing-based cryptography.

The prime order case

Eventually, it's important to recall why "primes orders" are interesting with the DLP: that's because of the Pohlig-Hellman algorithm, whose worst complexity case is that of the baby-step-giant-step algorithm when the order is prime.

Pohlig-Hellman basically is just like the CRT for RSA, it allows us to work in smaller, easier groups if the order of our initial group isn't prime.

In that kind of setup, it makes sense to have a large prime order, since all subgroups of our initial group must divide its order, therefore we're sure that Pollard-Rho is as hard as it can get.

The ECDLP case

Interestingly, the best (general) known attack (see this) on elliptic curve cryptography is a combination of both the Pohlig-Hellman and the Pollard-Rho algorithms. If you denote $l$ the largest prime divisor of $n$, this attack is able to tackle the ECDLP in only $O(\sqrt{l})$ time, hence why we'd want to have large prime divisor in our order $n$...

Notice that for anomalous curve, that is elliptic curves over a field $F_p$ whose EC order is also $p$, we have attacks that are running in polynomial time! See Satoh and Araki here, or Semaev, or Smart:

In practice the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the finite field

(emphasis mine)

Notice that in general, if $n−1$ is a product of small primes, then the Pohlig–Hellman algorithm can solve the discrete logarithm problem in this group efficiently, which is typically a reason why we'd pick a safe prime when dealing with the DLP: it ensures we have a "large" prime in the decomposition of $n-1$.

On the order of EC vs basepoint orders

Notice that the order of a curve is basically the number of rational points on that elliptic curve. If we are working over $F_p$, then we know that that number of points in our EC is $p+1-t$ where $t$ is the Frobenius trace of the curve. By Hasse's theorem we also know that $t$ is between $-2 \sqrt{p}$ and $2 \sqrt{p}$.

But in ECC we are usually working on a subgroup of an elliptic curve defined by a basepoint. The order of the basepoint is a prime divisor of $p+1-t$ by Lagrange theorem.

So which one would you like to be a safe prime? I'd assume the subgroup generated by a given basepoint.

This is also true for pairing-based cryptography: the pairings are defined over a subgroup of the EC group. Typically Tate pairing assumes $k>1$, $\#E(F_p) = hn$, for $n$ a prime, and it works in the subgroup of order $n$ of that elliptic curve.

How to construct one?

Sadly, as I told you at the start, I do not know of a pairing-friendly curve whose subgroup's order is a safe prime. It should be possible to construct one, but I didn't have time (yet) to write a search script that would produce one. How do we do? Well, I'm afraid the easiest way is "trial and error" there!

Barreto and Naehrig have given a method for curves of prime order with $k = 12$, which has been "extended" to curves with $k= 3, 4, 6$ by Freeman.

Sadly, I'm not aware of an open source implementation allowing you to easily try and generate these curve.

Sean avatar
yt flag
Thanks again for the points! Really appreciated.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.