Have I understood pedersen commitment correctly?

Question

I want to do a one-sided integer commitment scheme. I.e. the whole process must be non-interactive where I at one point first publicly reveal some data and then at a later time reveal the committed integer which then can be verified.

In the pedersen commitment scheme we have six pieces of data $p$, $c$, $g$, $h$, $x$, $r$. $p$ is the prime order of the group. $c$ is simply $g^x·h^r \bmod p$. $g$ and $h$ are generators of $\mathbb Z_{p\mathbb Z}^*$. $x$ is the committed value and $r$ is a random element.

The scheme would then proceed as follows.

1. We choose a prime $p$ and generators $g$ and $h$. Can this be some fixed elements that are used every time or must we pick new ones for each run? If so, how? $p=2g+1$ would work, but what about $h$?

2. We pick our committed $x$ and generate a random element $r$ in the group.

3. We calculate $c$ and publish $p$, $g$, $h$ and $c$.

4. To reveal, we simply reveal $x$ and $r$, which then can be verified by recalculating $c$.

Would this be a correct implementation or have I misunderstood something?

Answer 1

r can only be reused by coincidence (i.e., it must be selected independently each time).
There is not problem with giving multiple commitments to the same x.
In the following, p will be the modulus and q will be the order of the group.

Definition: $\:$ range(n) is the set of non-negative integers that are less than n


The following conditions guarantee the perfect hiding property:

p and q must be primes such that $\:p-1\:$ is a multiple of q.
g and h must satisfy $\: \operatorname{mod}\left(g^{\hspace{.01 in}q},p\right) = \operatorname{mod}\left(h^{\hspace{.01 in}q},p\right) = 1 \neq \operatorname{mod}(h,p) \;\;$.
r must be generated as a random element of range(q).


The following conditions are for the computational binding property:

p and q must be odd primes such that $\:p-1\:$ is a multiple of q. $\;\;$ Set $\: j = \frac{p-1}q \;$. $\;\;$ For k the security parameter, q should be bigger than $2^{\hspace{.005 in}2\cdot k}$ and p should be about the size of an RSA modulus (for the
same security parameter). $\;\;$ I'm not aware of any way for an adversarial committer to benefit from
being able to choose the particular p and q. $\:$ I'm also not aware of any argument that there is no
way for an adversarial committer to benefit from that. $\:$ h must be determined before u is generated.
Next, generate u as a random element of range(p-3) and then set $\: g = \operatorname{mod}\left((2+u)^{\hspace{.02 in}j},p\right) \;$.
(It does not matter whether or not u gets revealed.) $\:$ Finally, x must be an element of range(q).

My understanding of how to generate p and q is to either

find an odd prime q and then search for even j such that $\:\left(\hspace{.02 in}j\hspace{-0.03 in}\cdot \hspace{-0.03 in}q\right)+1\:$ is prime
or
choose j to be even, then search for odd q such that q and $\:\left(\hspace{.02 in}j\hspace{-0.03 in}\cdot \hspace{-0.03 in}q\right)+1\:$ are both prime

although I think there's no useful proven bound on the
average amount of time either of those methods would take.


At least heuristically, $\:\operatorname{mod}\left(2^{\hspace{.02 in}j},p\right)\:$ is highly likely to satisfy the conditions required for h.
If it does, then I think it would be the canonical value of h. $\;\;$ If it doesn't, then I would recommend
trying values v in range(p-5) until $\:\operatorname{mod}\left((3+v)^{\hspace{.02 in}j},p\right)\:$ satisfies the conditions required for h.
When v is sampled randomly from range(p-5), the probability that
$\operatorname{mod}\left((3+v)^{\hspace{.02 in}j},p\right)\:$ does not satisfy those conditions is less than $\:\frac1q\:$.

Answer 2

Yes, $p$, $g$ and $h$ are system parameters. $g$ and $h$ only need to generate large prime subgroups of $\mathbb{F}_p^{*}$, and the equation $p=2g+1$ is not required. (In fact, if I understand what you mean correctly, it does not always suffice as $-1/2$ has the same order as $2$)

It is important that $g$ and $h$ not be related by a known equation of the form $g=h^k$, because in that case the commitment is easily forgeable. One solution is to fix $g$ and $h$ to be small integers, and verify they have large prime order modulo some prime $p$.