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?