If Barreto-Naehrig Curves are suitable for pairing-based cryptography, can I use the library available at Optimal ATE Pairing?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Why can't you? The BN curves are suitable for crypto application and computing curves order is obvious. You can also take a look over the web to the work of Frederik.Vercauteren, another expert in this domain. $\endgroup$– Robert NACIRICommented Feb 9, 2015 at 6:20
-
$\begingroup$ BN curves are actually a very good choice for pairing based crypto from a security-performance tradeoff point of view. Can you use the library? Sure, if you like it...but there are also some others. $\endgroup$– DrLecterCommented Feb 11, 2015 at 22:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
You can, with the right parameter sizes (384-bit prime instead of the older 256-bit).
Pairings can be attacked in two fronts: the elliptic curve or the extension finite field. The security of the pairing will be the the one that is easiest to break.
Previously, a BN curve using an elliptic curve over a 256-bit prime provided 128 bits of security; it was the "perfect" case since the elliptic curve provided 128 bits and the extension field also provided 128 bits.
After Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case, things changed in the extension field case, and it's hard to give a concrete estimate since the paper handles asymptotics and we'd need to have concrete implementations to have more accuracy. But the paper estimates that the prime size must be doubled (i.e. from 256 bits to 512 for 128 bits of security). Aurore Guillevic estimates that it should be changed to 448 or 512 bits. However, further analysis in Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-based Cryptography, indicate that 384 bits should be enough.
So, if you use $p$ with 384 bits, you should be fine, but the performance won't be very good. In this case, the elliptic curve provides 192 bits of security while the extension field provides 128 bits, and we're stuck with the smaller value.
As an example, Zcash chooses the BLS12 pairing for the 128-bit security level since, due its structure, it is a 256-bit group (instead of a 384-bit group in BN) which makes some things faster. The underlying prime is the same size, though (384 bits).
-
$\begingroup$ Another reason why BN curves are interesting is that they are prime-order and always form "half-pairing cycles", which are potentially useful for recursive proof systems. I.e. if we have a BN curve over $\mathbb{F}_p$ with prime order $q$, then there is also a (non-pairing-friendly) curve over $\mathbb{F}_q$ with order $p$. This script can find such cycles, also with other interesting properties like high 2-adicity, twist security, and efficient isogenies for simplified SWU hash-to-curve: github.com/daira/curvesearch/blob/master/halfpairing.sage $\endgroup$ Commented Mar 19, 2021 at 9:31
$\begingroup$
$\endgroup$
According to Trevor Perrin's post from 2016, Barreto-Naehrig curves are not secure enough:
The attack is relevant to pairing-friendly curves (like BN) that support a "pairing" operation. A pairing maps points on the elliptic curve to values in some "extension field". Security depends on both the EC-DLP for the elliptic curve, and also DLP on the extension field.
256-bit BN curves have a field prime p of 256 bits and an "embedding degree" of 12, so the extension field is mod p^12, where p^12 has 3072 bits. The hope was that 256-bit EC-DLP and 3072-bit DLP would both have security ~128 bits, so this would be nicely matched.
However, Kim and Barbulescu showed that DLP where the modulus is a 3072-bit (prime^12) is easier than DLP for a 3072-bit prime. How much easier isn't clear, though by a "crude and naive estimation" they suggest increasing the size of relevant curves by a third (Section 6). Mehdi Tibouchi has a similar estimate [22]: "after this attack, 256-bit Barreto-Naehrig curves no longer offer 128 bits of security, but perhaps closer to 96 or so".
