Score:3

BLS signature scheme with G_1 = G_2

ma flag

The Wikipedia page for BLS digital signature describes a scheme with only two groups, $G$ and $G_T$, and a bilinear pairing $e: G \times G \rightarrow G_T$. To the best of my understanding, in such a scheme both public keys and signatures would belong to the same group $G$, signature verification being performed by comparing elements of $G_T$.

Looking around for real-world implementations of BLS, such as blst, I noticed however that three groups are used instead, namely $G_1 \neq G_2$ (one for public keys, one for signatures), plus $G_T$, codomain of the bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$.

I am wondering if real-world, secure implementations of BLS exist using the same group for both public keys and signatures (i.e., $G_1 = G_2$), as described in the relevant Wikipedia entry. If such implementations do not exist, I would be interested to know what their vulnerability is (and I am wondering if we should update the Wikipedia page!)

Marc Ilunga avatar
tr flag
Doesn't the type of pairing matter mainly from performance? Although, yeah provable security may depend on the type of pairing as well.
ma flag
Context: I am a PhD student in distributed computing and I am designing a protocol that I believe might work if only any secure BLS implementation existed for $e: G \times G \rightarrow G_T$, so if anyone can point me to one, it'd be a big step forward!
Bean Guy avatar
in flag
You can use the Weil pairing over any pairing-friendly elliptic curve. But as @MarcIlunga said, you will have much worst performance than if you use the reduced Tate pairing or the Ate one.
Score:3
ru flag

TL; DR

It is possible to build secure BLS signatures schemes of this type, but for the same level of security shorter signatures can be produced by ECDSA which negates the short-signature value of BLS.

History

Boneh-Lynn-Schacham (BLS) siganatures were an early (2004) proposed application of pairing-based cryptography to produce digital signatures which consisted of only a single group element (contrast with (EC)DSA signatures which consist of two integers of size commensurable with the group order). If the representation of a group element can be condensed to the size of the group order and the group does not offer a faster than 4th root discrete logarithm solution, then BLS signatures are will provide a shorter signature solution over ECDSA signatures of the same security. The idea pre-dates subsequent work in producing "pairing-friendly" curves that allow for a much wider range of parameters than were available at the time of the BLS paper. When BLS produced their initial work, the main ideas for pairing-based cryptography were based around super-singular curves and "distortion maps" which functionally allowed pairing functions of the form $G\times G\to G_T$. Subsequently, more general constructions began to appear and a taxonomy was introduced by Galbraith, Paterson and Smart in their paper Pairings for Cryptographers, in which the pairings used in the original BLS work were termed ``type 1'' pairings. They also introduced the terminology type 2 and type 3 pairings for pairings of the form $G_1\times G_2\to G_T$ with $G_1\neq G_2$. Constructions such as BLS were easy to adapt to type 2 and type 3 signatures, with signature size being determined by the smaller group. Shortly after the taxonomy was introduced, a great many constructions were found that allowed very efficient type 2 and type 3 constructions and type 1 began to fall into disuse (see Steven Galbraith's blog from 2014). For historical reasons then, BLS is often described using the notation of the original paper (which uses what we now term a type 1 pairing) and implemented using more modern pairings. The reason for the deprecation of type 1 pairings lies in the interplay between security and signature size.

Security of pairing-based cryptography

The practically-assessed security of well-designed pairing-based systems comes down to the difficulty of the discrete logarithm problem in the various groups involved. For elliptic curve pairing there are essentially two approaches: using a generic square root algorithm (such as Baby-Step-Giant-Step or Pollard's kangaroo) on one of the left hand groups or using an index calculus attack on the group $G_T$ which is the multiplicative group of a finite field. In the early days of pairing based cryptography, the index calculus attack was believed to be roughly as hard as a number field sieve (NFS) attack on a prime field of similar size, but subsequent work by Kim and Barbulescu produced the Extended Tower Number Field Sieve (xTNFS) which showed that for many pairing-friendly constructions faster attacks existed. This work made the costing of the security of pairing-friendly cryptography a little arcane, but estimates were still relatively straightforward.

Comparison of 128-bit secure signatures

Suppose then we hope to produce signatures with 128-bits of security. One can achieve this using ECDSA and a 256-bit curve over a prime field and have signatures 512-bits in size. Can BLS do better with various constructions?

If we restrict ourselves to type 1 pairings that were available when BLS chose their original work, we have $G_T=\mathbb F_{p^2}^\times$ where the elliptic curve is defined over $\mathbb F_p$ so that signatures will be $\lg p$ bits in size*. The NFS attack would require the field $\mathbb F_{p^2}$ to be roughly 3072-bits in size in order to achieve 128-bits of security. his would make $p$ roughly 1536-bits in size and similarly our signatures would be of this size and significantly longer than ECDSA.

If we turn to some type 2 pairing proposals that were hoped to provide 128-bits of security prior to Kim and Barbulescu's work, a popular choice might be the Barreto-Naehrig construction that maps to $\mathbb F_{p^{12}}^\times$. Using the naive NFS costing we could take $p^{12}$ around 3072-bits and hence $p$ around 256-bits which would still afford enough security to generic square root attacks. This would give signatures of size 256-bits which saves a factor of 2 over ECDSA an is in some sense the best that one might hope for.

Sadly, the xTNFS attack of Kim and Barbulescu improves the index calculus estimate to allow an attack of roughly 100-bits, so that the 256-bit long signatures of BN256 do not afford 128-bits of security. In their paper Updating key size estimations for pairings Barbulescu and Duquesne revisited some popular pairing-friendly constructions and concluded that 128-bits of security could be provided by Barreto-Naehrig curves with $p$ around 462-bits (with $p^{12}$ therefore around 5544-bits). These are large an unwieldy curves, but do provide a signature size saving over ECDSA.


(*) - I omit discussion of pairing constructions in small characteristic where work of Granger, Joux et al show that the constructions are horribly unsuitable.

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.