Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from security.stackexchange.com May 1 '13 at 22:53

This question came from our site for Information security professionals.

    
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. –  Ricky Demer May 2 '13 at 6:32

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
The j in my answer is called the cofactor. $\:$ –  Ricky Demer May 4 '13 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$.

share|improve this answer
    
What do you mean by "prime subgroups"? $\:$ (Just prime-order subgroups would not be sufficient.) –  Ricky Demer May 2 '13 at 6:21
    
Large prime order is to ensure discrete log is sufficiently hard. –  Watson Ladd May 2 '13 at 23:16
1  
For the hiding property, $g$ must be in the subgroup generated by $h$. $\:$ –  Ricky Demer May 2 '13 at 23:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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