What does it mean for g and h to be indendent in pedersen commitments?

Question

I'm looking at a research paper about the insecurity of a specific (wrong) usage of Pedersen commitments.

First, I'll go through the steps of Pedersen commitments, so that it can be shown if I have a basic misunderstanding.

My understanding of Pedersen commitments

Firstly we say Bob wants Alice to commit to a message, therefore he generates two prime numbers p and q.

p <--- random prime q <--- random prime

Bob then generates the generator g, which is of the order of q and is in the group $Z_{p}^*$.

g <--- $\in Z_{q}^*$

He then picks a secret value x in $Z_{q} $:

x <--- $\in Z_{q} $

x is the secret key, which he uses to derives the public key:

$h = g^{x} mod p $

Alice now wants to commit to a specific message, and has access to the public key and secret key of bob. She first picks the message m and a random integer r, and then computes her commitment c:

c = $ g^{m}*h^{r}$

Alice can now send the commitment to Bob. When Alice wants to reveal her commitment, she sends m and `r``to Bob. Bob is now able to do the same computation and compare.

Application in voting, and issue of independence

In the article referenced earlier, the scheme is used to confirm the integrity of a set of shuffled votes. In this context, a list of n encrypted votes are denoted by $ m_{1},...,m_{n} $. The pedersen commitment for a list of votes is then computed by:

$ c = G_{1}^{m_1} ... G_{n}^{m_n} * H^{r}$

And then the paper says this about the values of G and H (there may be some notation confusion, since I am used to using lowercase g and h for the generator for generator and PK, while the paper opts for capital letters). But then the paper states the following issue that may arise:

"If independence is violated between H and one single value Gi, then the extended commitment c can be open for any vector of alternative messages m′1,..., m′n. If this happens, then the whole shuffle proof argument collapses, i.e., it is possible to construct a fake proof for an incorrect shuffle"

I'm a little bit confused as to what it means for the values of $G_{i}$ and H to be "independent", and what it likely means when we have several versions of G, so I have two questions:

1

if we have n G's, then does that mean that the group that we are working in needs to have n generators?

2 How can there be one H, and several generators? if H is computed by using G, then which G is used to compute the public key H. Maybe I am misunderstanding something basic about the construction outlined in the paper?

Answer 1

I'm a little bit confused as to what it means for the values of $G_i$ and $H$ to be "independent",

Actually, the paper gave a fairly decent definition:

Independence means that respective discrete logarithms $h = \log_G H$ and $g = \log_H G$ are unknown to everyone.

That is, no one is supposed to know the solution $x$ to $G^x = H$

However, because we're working with multiple generators, it turns out that we need a stronger statement: no one knows a nontrivial solution $(a_1, a_2, ..., a_n, b)$ for the relation $G_1^{a_1} \cdot G_2^{a_2} \cdot ... \cdot G_n^{a_n} \cdot H^b = 1$, where the trivial solution is $a_1 \equiv a_2 \equiv ... \equiv a_n \equiv b \equiv 0$.

However, the same idea applies.

if we have $n$ $G$'s, then does that mean that the group that we are working in needs to have $n$ generators?

Yes. Actually, we have a lot more - if we're dealing with a group with a size $q$ where $q$ is prime, then there will be $q-1$ generators. Because we need $q$ to be at least 256 bits (to make the discrete log problem hard), that means that we have a huge number of generators available to us.

How can there be one $H$, and several generators? if $H$ is computed by using $G$,

Actually, we don't compute $H$ using $G$, we pick it independently.

Now, if you go back to the original Pedersen paper, he did suggest that the verifier select $H$ (and hence might do that selection by picking a random value $h$ and computing $H = G^h$, and giving $H$ (but not $h$) to the prover); that way, the verifier could be confident that the prover didn't know the discrete log.

However, nowadays we generate $G$ and $H$ independently (so literally no one knows the relationship) - this approach obviously extends to multiple $G$ values.