Score:2

Encryption within the groups of BLS12-381

gl flag

I have been investigating libraries that implement operations and protocols involving BLS12-381 curves. I have noticed an absence of libraries that support encryption over (either of) the groups G1 and G2 that are defined by the BLS12-381 curves.

Is there some cryptographic reason that encryption (say, ElGamal encryption) over these groups is not appropriate, or is this instead just an indication that BLS12-381 libraries are typically designed with signatures and SNARKs in mind?

884d88baaa avatar
gl flag
An aside: I had wondered whether encryption is not supported because the pairing associated with the BLS curves makes decisional Diffie-Hellman easy and renders ElGamal insecure. However, my understanding is that this pairing attack on ElGamal only works for symmetric pairings, whereas the pairing of BLS is asymmetric.
DrLecter avatar
cn flag
BLS12-381 represents type 3 pairings - so no efficiently computable isomorphisms between G1 and G2. So DDH holds in each group. You can safely use ElGamal when you either keep everything in G1 or G2. I guess libraries do not support it because its practical use mostly shows up for SNARKS - where it originates from (and most other use is research oriented).
poncho avatar
my flag
Here's one conceptual way to look at it: BLS12-381 has additional structure over a standard elliptic curve; this structure can be used both by the designer and the adversary. However, if the designer has no use for it (because he's doing something that could be done with a standard elliptic curve), then he's giving the adversary an additional tool for no reason.
Score:1
ru flag

In terms of the IND-CPA properties, the pairing can also be applied to create non-trivial bilinear map $\mathbb G_2\times\mathbb G_2\to\mathbb G_T$ to that the decisional Diffie-Hellman problem is easy in $\mathbb G_2$. Thus $\mathbb G_2$ should not be used for El Gamal constructions where ciphertext indistinguishability is required. Applying the pairing to $\mathbb G_1\times\mathbb G_1$ gives a trivial map, but one must be careful to use only elements of prime order $\ell$. The pairing can be extended to $(h\ell)$th roots of unity for a cofactor $h$ of moderate size and for the BLS construction, there is a distortion map from the order $h$ subgroup of the small field to the order $h$ subgroup of the large field and so DDH is solvable with advantage when that subgroup is used.

The main reason why BLS12-381 groups are not used is likely to be a question of efficiency. The security of private key recovery for EL Gamal in both groups is believed to be 126-bits, using the XTNFS attack of Barbulescu et al. The same/better level of security is attained by the NIST-P256 and Curve 25519, but the operands for these curves are over 30% smaller and so require less computation and bandwidth.

884d88baaa avatar
gl flag
Thank you; I have some follow-up questions. First, ElGamal is not IND-CCA secure in general, regardless of pairing considerations. Did you mean to say IND-CPA secure? Second, where can I find the technique for constructing this non-trivial mapping G_2 X G_2-->G_T from the pairing? Third, I am not sure how to interpret what you say in terms of best practices for encryption. My understanding is that G_1 is standardised as a group of prime order, and so there are no nontrivial subgroups of G_1. What subgroup did you mean when you said that DDH is solvable in "that subgroup"? Many thanks!
Daniel S avatar
ru flag
1. Yes apologies that should read CPA and has now been corrected. 2. The map can simply be the Weil pairing as computed by Miller's algorithm. 3. Yes standards specify that the prime order subgroup should be used, but if one is not careful to sanitise inputs, adversaries can introduce invalid parameters (similar to the small subgroup attack). In BLS 381, the full elliptic curve group over the prime field has a subgroup of order `0x396c8c005555e1568c00aaab0000aaab`
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.