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?

  • $\begingroup$ The non-interactive version of information-theoretically hiding commitment (such as Pedersen commitment) uses a setup string which the verifiers must trust was generated in a way that was not significantly controlled by the committer. $\:$ To be "really" non-interactive, a commitment scheme should be perfectly binding. $\endgroup$
    – user991
    Commented May 2, 2013 at 6:32
  • $\begingroup$ A group of a hidden order is useful to commit to an integer. Pedersen commitment scheme is for an element of $\mathbb Z/n \mathbb Z$, ring of residues modulo group order, which is a prime divisor of $(p-1)$. $\endgroup$ Commented Jan 19, 2015 at 21:24

2 Answers 2


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
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\:$.

  • $\begingroup$ The j in my answer is called the cofactor. $\:$ $\endgroup$
    – user991
    Commented May 4, 2013 at 22:03

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$.

  • $\begingroup$ What do you mean by "prime subgroups"? $\:$ (Just prime-order subgroups would not be sufficient.) $\endgroup$
    – user991
    Commented May 2, 2013 at 6:21
  • $\begingroup$ Large prime order is to ensure discrete log is sufficiently hard. $\endgroup$ Commented May 2, 2013 at 23:16
  • 1
    $\begingroup$ For the hiding property, $g$ must be in the subgroup generated by $h$. $\:$ $\endgroup$
    – user991
    Commented May 2, 2013 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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