3
$\begingroup$

What family of bilinear pairing is recommendable for BLS signature when the overriding criteria is compactness of the signature, as desirable for something to be keyed-in from printout, or embedded in a small QR-code?

Is there something giving signature size lower than ≈384 bit for 128-bit conjectured security, as in this draft RFC, which is no more compact than a more conservative and faster short Schnorr signature?

What's the current status of Barreto/Naehrig curves (Pairing-Friendly Elliptic Curves of Prime Order, in proceedings of SAC 2005 and eprint)?

Assuming that's no longer in use: any info about what Paulo S. L. M. Barreto reported has been successfully used for VAT receipt purposes in the province of São Paulo (Brazil) 2008-2013, with 160-bit signatures of security then conjectured roughly equivalent to RSA-1024?

Brazil 2008 VAT receipt

$\endgroup$
1
  • 1
    $\begingroup$ Can't answer the other parts, but BN curves are not really used anymore because of the Number Field Sieve (ellipticnews.wordpress.com/2016/05/02/…). For the same security level, BLS curves are faster $\endgroup$ Feb 15, 2023 at 18:25

1 Answer 1

2
$\begingroup$

I don't know if the landscape has changed much since 2019, but looking at the paper A taxonomy of pairings, their security, their complexity by Barbulescu et al we want a pairing-friendly curve with 128-bits of security and the smallest possible $q$. The best option seems to be in table 11 using the cubic twist variant of BLS coined k27method66 by Zhang and Lin in their paper Analysis of optimum pairing products at high security levels where a 300-bit $q$ is possible (the pairing landing in the field $q^{27}$).

For Barreto-Naehrig curves at the 128-bit security level, Barbuescu et el suggest a base prime $q$ of 462 bits.

ETA: To be explicit about the k27method66 curve with 300-bit prime, the recipe (per section 5.4 of the Barbulescu paper) is to choose a 15-bit $u$ and set $$q=(u-1)^2(u^{18}+u^9+1)/3+u$$ $$r=(u^{18}+u^9+1/)3$$ then if $q$ is prime, with these choice a curve with complex multiplication with discriminant 3 over $\mathbb F_q$ will have group size divisible by $r$ and $r$ will divide $q^{27}-1$ which fits the criteria for a pairing taking values in $\mathbb F_{q^{27}}$. In the table we see to take $u=2^{15}-2^{10}+2^3+1$ and a little sage:

u = 2^15-2^10+2^3+1
q = (u-1)^2*(u^18+u^9+1)//3+u
print(q.is_prime())
print(q)
E = EllipticCurve(GF(q),[0,-2])
r = (u^18+u^9+1)//3
print(r.is_prime())
print(r)
print((q^27-1)%r)
print(E.cardinality()%r)

produces

True

361865065320728439833719086758866208857114634221052000919029745553653612029141017881951817

True

358925642337106139753780938745883044679182292122981674007816040062299252055237641

0
0

Telling us that the curve $y^2=x^3-2$ admits a pairing from $E(\mathbb F_q)\times\mathbf E(\mathbb F_{q^{27}})\to \mathbf F_{q^{27}}^\times$. Picking points $P_1$ and $P_2$ of order $r$ from the two curve groups should give generators for a non-degenerate pairing. A private key $s$ can produce public key $sP_2$ and signatures $sH$ where $H$ is a hash of the message to a point in $\langle P_1\rangle$. Note that using point compression we should be able to represent $sH$ in 299 bits ($q$ is actually only 298 bits long). Signature can be checked by the pairing relationship $e(H,sP_2)=e(sH,P_2)$.

$\endgroup$
5
  • $\begingroup$ I see the table 11, about method 6.6 at 128-bit security, and the line $k=27$ with $\log_2q=300$. But I fail to link that with Barbulescu's data k27method66.txt and k27method66-128-3.txt. And much more to grasp what signing and checking the corresponding 300-bit BLS signature would involve. $\endgroup$
    – fgrieu
    Mar 1, 2023 at 14:34
  • 1
    $\begingroup$ @fgrieu I've tried to expand on the construction. The costing files don't seem to include this case as they aim to get 175-bits of security for the multiplicative discrete logarithm problem for some reason. $\endgroup$
    – Daniel S
    Mar 1, 2023 at 16:17
  • $\begingroup$ Many thanks. I'm a step closer to understanding how signing and verifying would work. And at least I grasp that the arithmetic in $\mathbb F_{q^{27}}$ is going to require non-trivial work. I deffer accepting the answer until I study that more. I'm trying to iron out how much of draft-irtf-cfrg-bls-signature-05 and draft-irtf-cfrg-pairing-friendly-curves-11 apply, and why something from k27method66 is not included there. $\endgroup$
    – fgrieu
    Mar 2, 2023 at 12:13
  • $\begingroup$ I found this paper which I hope is somewhat relevant. They do consider $k=27$ but only starting at the 192-bit security level, and I do not get why. For now this is all flying at high altitude above my head, including their appendix B on arithmetic in $\mathbb F_{p^{27}}$; I do not even get if the math in that appendix is compatible or antagonist with what I think is the reference for method 6.6, subcase of $k≡9\pmod{18}$! $\endgroup$
    – fgrieu
    Mar 2, 2023 at 14:58
  • $\begingroup$ Happy to explain some of that paper in chat $\endgroup$
    – Daniel S
    Mar 2, 2023 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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