Create random element from group G in BLS Scheme

empty_stack

12/12/23, 1:27 PM

I hope this question is not too basic. I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by BLS scheme as described in this paper Compact Proofs of Retrievability in GO. I already implemented it with RSA and now I want to do the same with the BLS Scheme as described in section 3.3 on page 12. For simplicity it is symmetric.

It states that I should generate $s$ random elements: $ u_1 ... u_s \overset{{R}}{\leftarrow} G$ and this is where I'm not quiet sure how to interpret this.

Would it be sufficient to generate random numbers $x_1 ... x_s$ from $\mathbb{Z_p}$ (private key is derived from $\mathbb{Z_p}$) and use a generator $g$ of $G$ to calculate $u_s \leftarrow g^{x_s}$ for example? Or am I on the completely wrong track there?

Thanks and regards.

0 + 5

elliptic-curves

group-theory

bls-signature

ckamath

12/14/23, 4:47 PM

This should work since $G$ is cyclic and has order $p$ (and therefore $G$ and $\mathbb{Z}_p$ are isomorphic).

empty_stack

12/20/23, 11:08 AM

Would it be also sufficient enough to just generate the random numbers $x_1...x_2$ from $\mathbb{Z}_p$ if they are of the same order as $G$? So there would be no need to do $u_s \leftarrow g^{x_s}$.

ckamath

12/20/23, 1:36 PM

That does not work since the elements of $\mathbb{Z}_p$ and $G$ might look different (e.g., in the case where $G$ is defined using elliptic curves), and the way to "translate" from $\mathbb{Z}_p$ to $G$ is using the map $x\mapsto g^x$, where $g$ is a generator of $G$.

empty_stack

12/21/23, 3:03 PM

Okay so let $e: G_1 \times G_1 \rightarrow G_T$ be a bilinear map. $G_1$ is a BN256 (alt_bn128) elliptic curve. Now if i choose $u_1 ... u_s \overset{{R}}{\leftarrow} G_1$ every single $u$ will be a generator of $G_1$, right? Because if they are, I don't know i can compute the following, as stated in the paper: $\prod_{j=1}^s u_j$ because we would need to multiply the points, and multiplication of multiple points is not defined for elliptic curves. Or could the $\prod$ in this case simply be interpreted as a $\Sigma$ as we are working on curves?

ckamath

12/25/23, 8:56 PM

Yes, they are using the multiplicative notation for groups (instead of the additive notation). You can simply substitute the exponentiations with scalar multiplications and products with addition.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Create random element from group G in BLS Scheme

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.