I am reading a paper which defines an algorithm as following: Suppose for the BLS algorithm I have parameters (p,g , G, GT ,e) where , G and GT are multiplicative cyclic groups of prime order p , g is a generator of G and e: G X G --> GT.

Now the client choses a random x from Zp as secret key and from here the public key is derived as g^x.

Now this paper states that Let a <--R--G (which means that a is randomly chosen from the cyclic group G) be another generator of G.

But how is this possible? How can a cyclic group have two genertors. Is it possible ?

  • $\begingroup$ You basically have no idea what a generator of a cyclic group is; I suggest you actually study some algebra. $\endgroup$ – fkraiem Oct 12 '17 at 8:32
  • $\begingroup$ @fkraiem Basically some people on forum find it very interesting to give advices rather than answers. Thanks for yours. $\endgroup$ – skii Oct 12 '17 at 8:50
  • 4
    $\begingroup$ In a cryclic group of prime order, every single element except the neutral element is a generator. $\endgroup$ – tylo Oct 12 '17 at 9:15

How can a cyclic group have two generators?

I believe part of the difficulty you are running into is because, in cryptography, we use the word 'generator' in multiple distinct (albeit related) ways.

One meaning (which is what is intended here) is this: we say that an element $g$ is a generator for a group $G$ if the group of elements $\{ g^0, g^1, g^2, ... \}$ is precisely the group $G$; that is, every element $h \in G$ can be expressed as $h = g^i$ for some $i$, and conversely, for every $i$, $g^i \in G$ [1].

Now, the obvious question is: for a given cyclic [2] group $G$, is the choice of $g$ unique? It turns out that (as long as the order of the group is > 2) it is not. In fact (as mentioned in the comments), if the size of the group is prime, then every group element (other than the identity) happens to generate the entire group, and so (in this sense) there are also generators.

Now, to give you some perspective, I will give you another meaning we give 'generator' that isn't meant by this question. Sometimes, in a cryptographic protocol, we need to specify a public generator $g$ that will be used by both sides. A simple example of this is Diffie-Hellman, where one side computes and publishes $g^a$, and the other side computes and publishes $g^b$; both sides must use the same $g$ value for this to work. We call this common value the generator; yes, there are other values that are (in the first meaning) also generators for the group we're working in, however, they are not the generator as far as protocol is concerned.

[1]: for infinite groups, we also need to consider negative exponents; we don't worry about infinite groups that much in cryptography.

[2]: actually, the definition of a cyclic group essentially is "there exists a generator"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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