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

lk flag

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:


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?

poncho avatar
my flag
You might want to fix the link to the paper - to get to a link on your harddrive, we'd have to break into your system, and we're not supposed to admit we can do that...
NotQuiteSo1337 avatar
lk flag
embbarasing! fixed it!
poncho avatar
my flag
You sure that's the right paper?
NotQuiteSo1337 avatar
lk flag
oh geez, it's the german version, sry again
poncho avatar
my flag
It's still a final report about a public penetration test (run by the Swiss) on a voting system - it doesn't mention anything about Pedersen...
NotQuiteSo1337 avatar
lk flag
Now the right one is up! sry
my flag

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.


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.