Score:3

Bilinear pairing for compact BLS signature

ng flag

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

Aman Grewal avatar
gb flag
Can't answer the other parts, but BN curves are not really used anymore because of the Number Field Sieve (https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/). For the same security level, BLS curves are faster
Score:2
ru flag

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

fgrieu avatar
ng flag
I see the [table 11](https://eprint.iacr.org/2019/485.pdf#table.caption.27), 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](https://razvanbarbulescu.pages.math.cnrs.fr/Pairings/k27method66.txt) and [k27method66-128-3.txt](https://plmlab.math.cnrs.fr/razvanbarbulescu/razvanbarbulescu.pages.math.cnrs.fr/-/blob/fe5a092e263636af2d95090e82bc2dc51977f6f9/save-bdq/d-k27method66-128-3.txt). And much more to grasp what signing and checking the corresponding 300-bit BLS signature would involve.
Daniel S avatar
ru flag
@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.
fgrieu avatar
ng flag
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](https://datatracker.ietf.org/doc/pdf/draft-irtf-cfrg-bls-signature-05) and [draft-irtf-cfrg-pairing-friendly-curves-11](https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11) apply, and why something from k27method66 is not included there.
fgrieu avatar
ng flag
I found [this paper](https://arxiv.org/pdf/2002.11920.pdf#page=15) 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](https://eprint.iacr.org/2006/372.pdf#page=28), subcase of $k≡9\pmod{18}$!
Daniel S avatar
ru flag
Happy to explain some of that paper [in chat](https://chat.stackexchange.com/rooms/144304/pairings-for-bls-signatures)
I sit in a Tesla and translated this thread with Ai:

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.